来自Leetcode第144题二叉树的前序遍历
给定一个二叉树，返回它的前序遍历。
递归
递归很简单，在大二上就已经学过了，按根左右的顺序即可。
1
2
3
4
5
6
7
8
9
10
11
12
| List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null)
return ans;
ans.add(root.val);
if (root.left != null)
preorderTraversal(root.left);
if (root.right != null)
preorderTraversal(root.right);
return ans;
}
|
迭代
利用栈，首先根结点入栈，当栈非空，栈顶元素出栈，并且其值写入List，如果左右子树都非空，就右子树入栈再左子树出栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return ans;
stack.add(root);
while(!stack.empty()){
TreeNode temp = stack.pop();
ans.add(temp.val);
if(temp.right != null)
stack.add(temp.right);
if(temp.left != null)
stack.add(temp.left);
}
return ans;
}
|
莫里斯遍历
题解里有，好像之前也看到过，摸了咕咕咕