94.Binary Tree Inorder Traversal

94.Binary Tree Inorder Traversal

二元樹的中序遍歷
中序遍歷是左子樹->根結點->右子樹

走訪的原則是一直往左子樹走，直到沒有根沒止
如果到達沒節點的地方
馬上返回上一個走訪的節點並加入
然後轉移到右節點
重複一開的步驟

這個走訪的路程，可以用兩個解法來寫

1. 遞迴
   遞迴的程式碼滿抽象，不過多多參考我上面畫的圖和文字敘述，會很好理解

   void dfsfor94(List<Integer> ans, TreeNode root){
     if(root == null)
      return;
     dfsfor94(ans, root.left);
     ans.add(root.val);
     dfsfor94(ans, root.right);
   }
   

2. 堆疊
   堆疊的原理就是利用後進先出的原理
   把路徑上可以取得的左子樹先加進堆疊
   一發現沒有馬上取出節點並接入結果中
   堆疊有一個比較特別的點，就是停止的條件
   走訪的root沒有參考或者堆疊為空

   void stack94(List<Integer> ans, TreeNode root){
     if(root == null)
    return;
     List<TreeNode> stack = new ArrayList<>();
     while (root != null || !stack.isEmpty()){
    while (root != null){
      stack.add(root);
      root = root.left;
    }
    root = stack.remove(stack.size()-1);
    ans.add(root.val);
    root = root.right;
     }
   }