Binary Tree Traversal (Iterative)

Leave a comment

December 12, 2016 by oneOokay

Binary Tree Traversal Inorder/Preorder/Postorder : 全部都用Stack。(POSTORDER最难了)

Preorder:

两种方法:

  • 方法一:所有的node都从stack里面过一次:那么就是先把Root放到stack中,然后while loop pop出来,先加入右儿子if exist,再加入左儿子 if exist。之后继续while loop pop。
  • 方法二:仅把右儿子放到stack里面:那么从Root开始就把root的值放入ans中,把root的右儿子无论是否是null都放入到stack里面,接着左儿子走;继续while loop。

第一种我能想到的logic是:

Push ROOT into Stack (N = ROOT)//首先要把Root先放到Stack里面
    While (Stack is NOT empty)
        N = Stack.pop() -> Add to ans //因为首先放的都是ROOT,Preorder需要先输出
ROOT,所以当Stack.pop的时候就直接放入到ans中
//1. pop出来的为左儿子或者右儿子的时候,他们的left和right都为null,继续pop
//2. pop出来的为一个子树的Root,先把Root的右儿子放入Stack,再把Root的左儿子放入
Stack,使得左儿子之后可以先被pop出来
        if N.right != null : push N.right into Stack
        if N.left != null : push N.left into Stack

第二种Improve的版本是:只把N.right或者null(当N.right == null时)放入Stack中。要注意先把N.right放到stack里面,再N=N.left.

While (N != null || Stack is NOT empty)
    if (N != null) : 
        -> Add to ans
        push N.right into Stack 
        N = N.left//ans形成了一条从root往左儿子走的路径,而且一边走一边把ROOT的右
儿子加入到stack当中。当最终走到最左儿子的时候,stack顶端是第一个应该取的右儿子。
    else 
        N = stack.pop()

Inorder:每棵子树的最左儿子先输出。pop出来的点:向右下走

While (N != null || Stack is NOT empty)
    while (N != null) //找到每棵子树的最左儿子且记录下路径
        push N into Stack
        N = N.left
    N = Stack.pop()//顺着左路径往上走的过程中:如果存在右儿子,那么push入一个新的以
右儿子为顶点的左路径开始往下走。
    -> Add to ans
    N = N.right.

Postorder: 需要引入一个pre来记录先前pop出来的点与当前stack.peek的关系,这样来决定是继续往左下走,还是右下走,还是pop

Push ROOT into Stack
pre = ROOT
While (Stack is NOT empty)
    N = Stack.peek
    if N.left != null && 
       N.left != pre //正处于从左儿子往Root走的途中,N.left已经被处理过了。
       N.right != pre //正处于从右儿子往Root走的途中,N.left已经被处理过了。
       Stack.push(N.left)
    if N.right != null &&
       N.right != pre //正处于从右儿子往Root走的途中所以N.right已经被处理过了。
       N.left == pre || N.left == null //正处于刚处理完左儿子,或者左儿子为空,下
一个正要处理N.right
       Stack.push(N.right)
    else
       N = Stack.pop() //N为一个叶子节点或者N为一个左右儿子都已经被处理完的ROOT
       ans.add(N.val)
       pre = N //更新pre

PreOrder Code:

public List preorderTraversal(TreeNode root) {
 List ans = new ArrayList();
 if (root == null){
 return ans;
 }
 
 Stack s = new Stack();
 
 TreeNode cur = root;
 while (cur != null || !s.isEmpty()){
 if (cur != null){
 ans.add(cur.val);
 s.push(cur.right);//先push右儿子
 cur = cur.left;
 }else {
 cur = s.pop();
 }
 }
 return ans;
 }
    }

Inorder Code:

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

Postorder Code:

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>>();
        if (root == null){
            return ans;
        }
        
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = root;
        s.push(root);
        while (!s.isEmpty()){
            TreeNode cur = s.peek();
            if (cur.left != null && cur.left != pre && cur.right != pre){
                s.push(cur.left);
            }else if (cur.right != null && cur.right != pre && 
(cur.left == pre || cur.left == null))
            {
                s.push(cur.right);
            }else {
                cur = s.pop();
                ans.add(cur.val);
                pre = cur;
            }
        }
        return ans;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: