94. Binary Tree Inorder Traversal（二叉树中序遍历）

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

return [1,3,2].

递归：

 1 class Solution {
 2     List<Integer> res = new ArrayList<Integer>(); 
 3     public List<Integer> inorderTraversal(TreeNode root) {
 4           help(root);
 5         return res;
 6     }
 7     private void help(TreeNode root){
 8         if(root==null) return ;
 9         if(root.left!=null)
10             help(root.left);
11         
12         res.add(root.val);
13         
14         if(root.right!=null)
15             help(root.right);
16     }
17 }

非递归：

终极版:

 1 class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         Stack<TreeNode> s = new Stack<TreeNode>();
 4         List<Integer> res = new ArrayList<Integer>();
 5         while(root!=null||!s.isEmpty()){
 6             while(root!=null){
 7                 s.push(root);
 8                 root=root.left;
 9             }
10             if(!s.isEmpty()){
11                 root = s.pop();
12                 res.add(root.val);
13                 root = root.right;
14             }
15         }
16         return res;
17     }
18 }

利用辅助桟

 1 class Solution {
 2     
 3     public List<Integer> inorderTraversal(TreeNode root) {
 4         List<Integer> res = new ArrayList<Integer>(); 
 5         Stack<TreeNode> stack = new Stack<TreeNode>();
 6         TreeNode cur = root;
 7         while(cur!=null ||!stack.isEmpty()){
 8             while(cur!=null){
 9                 stack.push(cur);
10                 cur =cur.left;
11             }
12             cur = stack.pop();
13             res.add(cur.val);
14             cur =cur.right;
15         }
16         return res;
17     }
18    
19 }