94. Binary Tree Inorder Traversa

二叉树的中序遍历，可以是经典的递归写法。
能写成递归就可以写成迭代，但是迭代的话需要保存一下之前的结点。比如对root来说，这个结点在我访问完左半部分之后才需要访问，于是我们可以使用一个stack，保证其访问顺序对于包含root的左半部分来说是最后的。FILO。

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result =new ArrayList<>();
        inOrder(root,result);
        return result;
    }
    private void inOrder(TreeNode root,List<Integer> result)
    {
        if(root==null) return ;
        inOrder(root.left,result);
        result.add(root.val);
        inOrder(root.right,result);
    }
}

迭代：

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result =new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root==null)return result;
        TreeNode cur  = root;
       while(cur!=null || !stack.empty())
       {
        while(cur!=null)
        {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.add(cur.val);
        cur=cur.right;
    }
        return result ;
    }
    
}

之前的写法有点问题，主要是：
while(部分没有写对，我总是取栈的peek为start，导致迭代回到这个最初的peek时又接着往下取了，陷入了死循环。

while(!stack.empty())
      {
     TreeNode cur = stack.peek();
       while(cur!=null)
       {
           cur = cur.left;
          stack.push(cur);
       }
       cur = stack.pop();
       result.add(cur.val);
      if(cur.right!=null)
      stack.push(cur.right);
   }