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?
二叉树的前序遍历
实现
递归解决
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;
}
|
迭代
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;
}
|
参考
近期评论