题目：
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?
题解：
中序遍历：递归左 处理当前 递归右。
画图的话就是，之前离散老师教的，从root开始沿着子树画线，遍历完全树，每一个被画线画到2次的就表示遍历到了，依次写出就行了。
递归代码如下：
1 public void helper(TreeNode root, ArrayList<Integer> re){
2 if(root==null)
3 return;
4 helper(root.left,re);
5 re.add(root.val);
6 helper(root.right,re);
7 }
8 public ArrayList<Integer> inorderTraversal(TreeNode root) {
9 ArrayList<Integer> re = new ArrayList<Integer>();
10 if(root==null)
11 return re;
12 helper(root,re);
13 return re;
14 }
2 if(root==null)
3 return;
4 helper(root.left,re);
5 re.add(root.val);
6 helper(root.right,re);
7 }
8 public ArrayList<Integer> inorderTraversal(TreeNode root) {
9 ArrayList<Integer> re = new ArrayList<Integer>();
10 if(root==null)
11 return re;
12 helper(root,re);
13 return re;
14 }
非递归代码如下：
1 public ArrayList<Integer> inorderTraversal(TreeNode root) {
2 ArrayList<Integer> res = new ArrayList<Integer>();
3 if(root == null)
4 return res;
5 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
6 while(root!=null || !stack.isEmpty()){
7 if(root!=null){
8 stack.push(root);
9 root = root.left;
10 }else{
11 root = stack.pop();
12 res.add(root.val);
13 root = root.right;
14 }
15 }
16 return res;
17 }
2 ArrayList<Integer> res = new ArrayList<Integer>();
3 if(root == null)
4 return res;
5 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
6 while(root!=null || !stack.isEmpty()){
7 if(root!=null){
8 stack.push(root);
9 root = root.left;
10 }else{
11 root = stack.pop();
12 res.add(root.val);
13 root = root.right;
14 }
15 }
16 return res;
17 }