樹的非遞歸周遊

二叉樹的周遊很重要，在面試中，如果涉及到二叉樹的周遊，通常會要求使用非遞歸的方式

下面是三種周遊的非遞歸實作

前序周遊

public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();//傳回的數組
Stack<TreeNode> stack = new Stack<>();//棧用于存儲
stack.push(root);//根節點入棧
while (!stack.isEmpty()) {//棧不空的時候進行循環
TreeNode node = stack.pop();
if(node!=null) {
ret.add(node.val);//目前節點添加進入數組//先将右子樹壓入棧，保證出棧時是左子樹先出來
stack.push(node.right);
stack.push(node.left);
        }
    }
return ret;
}
      

後續周遊

public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node=stack.pop();
if(node==null) continue;
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
      }//前面的過程和前序周遊隻要左右子樹入棧順序有差别，左子樹先進，保證右子樹先出
//最後将得到的數組逆序輸出即可。因為原來的順序是根-右-左，倒叙後才是真正的後續周遊結果
Collections.reverse(ret);return ret;
}
      

中序周遊

public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while (cur!=null||!stack.isEmpty()){//目前通路的節點不為空且棧不空的時候
while (cur!=null){
stack.push(cur);
cur=cur.left;
           }//當cur是null，即是說到底了的時候
TreeNode node=stack.pop();
ret.add(node.val);//彈出元素的值入數組
cur=node.right;//cur更新為node.right
       }
return  ret;
}