144. binary tree preorder traversal 实现 参考

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
Input: [1,null,2,3]
1

2
/
3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

二叉树的前序遍历

实现

  • java

递归解决

1
2
3
4
5
6
7
8
9
10
public List<Integer> (TreeNode root) {
List<Integer> pre = new LinkedList<>();
if(root==null) {
return pre;
}
pre.add(root.val);
pre.addAll(preorderTraversal(root.left));
pre.addAll(preorderTraversal(root.right));
return pre;
}
  • java

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> (TreeNode node) {
List<Integer> list = new LinkedList<>();
Stack<TreeNode> rights = new Stack<>();
while(node != null) {
list.add(node.val);
if (node.right != null) {
rights.push(node.right);
}
node = node.left;
if (node == null && !rights.isEmpty()) {
node = rights.pop();
}
}
return list;
}

参考