二叉樹的中序遍歷，可以是經(jīng)典的遞歸寫法。
能寫成遞歸就可以寫成迭代，但是迭代的話需要保存一下之前的結(jié)點(diǎn)。比如對(duì)root來說，這個(gè)結(jié)點(diǎn)在我訪問完左半部分之后才需要訪問，于是我們可以使用一個(gè)stack，保證其訪問順序?qū)τ诎瑀oot的左半部分來說是最后的。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 ;
    }
    
}

之前的寫法有點(diǎn)問題，主要是：
while(部分沒有寫對(duì)，我總是取棧的peek為start，導(dǎo)致迭代回到這個(gè)最初的peek時(shí)又接著往下取了，陷入了死循環(huán)。

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);
   }