Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
切记p节点初始时指向root.left。代码如下：
1 public class BinaryTreeInorderTraversal {
2 public ArrayList<Integer> inorderTraversal(TreeNode root) {
3 ArrayList<Integer> inOrder = new ArrayList<Integer>();
4 if (root == null)
5 return inOrder;
6 Stack<TreeNode> s = new Stack<TreeNode>();
7 s.add(root);
8 TreeNode p = root.left;
9 while (!s.empty()) {
10 while (p != null) {
11 s.add(p);
12 p = p.left;
13 }
14 TreeNode n = s.pop();
15 inOrder.add(n.val);
16 p = n.right;
17 if (p != null) {
18 s.add(p);
19 p = p.left;
20 }
21 }
22 return inOrder;
23 }
24 }