题目要求
1
2
3
4
5
6
7
8
9
10
11
12
| Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
|
中序遍历树，并将遍历结果添加到数组中。分别用递归和循环的方式结局。
递归
核心的思路就是先递归左侧子节点，之后读取中间节点的值，再递归右侧子节点。
1
2
3
4
5
6
7
8
9
10
11
12
| public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
inorderTraversal(root, result);
return result;
}
public void inorderTraversal(TreeNode root, List<Integer> result){
if(root==null) return;
inorderTraversal(root.left, result);
result.add(root.val);
inorderTraversal(root.right, result);
}
|
循环
这里需要利用栈的数据结构。如果当前节点存在左子节点，则继续遍历左子树直到最后一个左子节点。然后依次处理栈中的元素。如果栈顶元素有右子节点，则将其右子节点压入栈中作为root，再继续遍历root的左子节点。当root和stack都为空时，遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root==null) return result;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
do{
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.add(root.val);
root = root.right;
}while(!(stack.isEmpty() && root==null));
return result;
}
|