二叉树的非递归遍历

题目

关于树的非递归前中后序遍历,链接分别为:
http://www.lintcode.com/zh-cn/problem/binary-tree-preorder-traversal/
http://www.lintcode.com/zh-cn/problem/binary-tree-inorder-traversal/
http://www.lintcode.com/zh-cn/problem/binary-tree-postorder-traversal/

分析

但凡非递归实现,基本都靠栈来辅助。

前序非递归遍历

二叉树的前序非递归实现最简单,先将根结点入栈,然后开始循环,当栈空时退出循环。在循环时,先访问刚刚出栈的节点,然后将该节点的子节点按照先右后左,重复循环。


public class Solution {
    /*
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List preorderTraversal(TreeNode root) {
        // write your code here
        if(root == null){
            return new ArrayList();
        }
        Stack stack = new Stack<>();
        stack.push(root);
        List list = new ArrayList<>();
        
        while(stack.size() > 0){
            TreeNode temp = stack.pop();
            
            list.add(temp.val);
            if(temp.right != null){
                stack.push(temp.right);
            }
            if(temp.left != null){
                stack.push(temp.left);
            }
        }
        return list;
        
    }
}

中序非递归遍历

中序遍历遍历稍稍复杂一点点。

  • 中序遍历时,最先被访问的节点不是根结点,而是左子树上最“左”的节点,因此,需要先将根结点上所有左节点先入栈,然后开始出栈访问。
  • 出栈时,先访问当前节点,若当前节点存在右子树。则需要将右子树的所有左节点入栈
  • 栈空时遍历结束
  • 父节点每次会伴随遍历左子树时入栈

代码实现如下



public class Solution {
    
    void pushLeft(Stack stack, TreeNode node){
        while(node != null){
            stack.push(node);
            node = node.left;
        }
    }
    
  

    /*
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList inorderTraversal(TreeNode root) {
       if(root == null){
            return new ArrayList();
        }
        Stack stack = new Stack<>();
        ArrayList list = new ArrayList<>();
        TreeNode temp = null;
        
        pushLeft(stack, root);
        
        while(stack.size()>0){
            temp = stack.pop();
            
            list.add(temp.val);
            if(temp.right != null){
                pushLeft(stack, temp.right);
            }
          
        }
        return list;
    }
}

后序非递归遍历

这是最难的一种非递归遍历方式,原因在于,当一个元素出栈之后,既有可能是需要向下访问左右子树,也有可能是左右子树已经访问完毕,需要向上回溯。

举个例子,假设二叉树的某一部分有a、b、c三个节点,其中a是父结点,b、c分别是左右子树。a必然先于b、c入栈,由于b、c的存在,a在短暂出栈之后,又回重新回到栈内。而当b、c及其子树都访问完毕后,a元素会再次出栈,此时无需再访问b、c,而需要回溯a的父节点。

从上面的例子可以看出,当仅仅只有a出栈时,无法判断此时应当向下探索子树,还是向上回溯祖先。当然,如果通过给TreeNode增加一个字段visited,来标记是否访问过,这道题目就又会简单多了。但如果不允许通过各种标记形式来解决这个问题呢?

其实从上面的分析就可以看出来,如果我们知道此时应当下寻还是上溯是,就可以判断如何处理当前出栈的节点了。因此,可以通过增色一个变量,记录下来前一次访问的元素,通过与前一次访问的元素进行对比,就可以知道当前是在下寻还是在上溯。具体来说,一共有这么几种情况:(记前一次访问的节点为last,当前节点为temp)

  • last为空,此时尚未访问过任何节点。直接将根结点和其左右子树(如果存在的话),按照中、右、左的顺序入栈
  • last.left = = temp,说明上一次访问的是父节点,此时正在访问左子树,从上往下。如果该节点存在左右子树,则应当将当前节点、右子树、左子树依次入栈,并将last设置为当前节点。否则说明它是叶子节点,访问并将last设置为当前节点
  • last.right = = temp,说明正在访问右子树,处理方法和前一步一致
  • temp.left = = last, 说明正在回溯,刚刚访问完了左子树,并且temp不存在右子树。直接访问temp节点,并将last置为当前节点
  • temp.right = = last,说明正在回溯,刚刚访问完右子树,直接访问temp节点,并将last设置为temp
  • 还有一种情况,就是temp、temp的左右子树与last没有关系,last的左右子树也和temp没有关系,last和temp可能是兄弟,也可能没有直接关联。不管什么情况,只需要考虑当前temp节点,将当前节点及子树按照合理的顺序入栈即可。当然,若该节点不存在子节点,则直接访问,随后将last置为当前节点

代码实现如下:



public class Solution {
    
    /*
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List postorderTraversal(TreeNode root) {
        // write your code here
        List list = new ArrayList<>();
        if(root == null) return list;
        
        Stack stack = new Stack<>();

        TreeNode temp = null;
        TreeNode last = null;
        stack.push(root);
        
        while(stack.size()>0){
            temp = stack.pop();
            
            if(last != null){
                
                if(last.left == temp || last.right == temp){
                    
                    if(temp.right != null){
                        stack.push(temp);
                        stack.push(temp.right);
                        
                        if(temp.left != null){
                            stack.push(temp.left);
                        }
                        continue;
                    }else{
                        if(temp.left != null){
                            stack.push(temp);
                            stack.push(temp.left);
                            continue;
                        }else{
                            list.add(temp.val);
                            last = temp;
                            continue;
                        }
                    }
            
                    
                }else if(last == temp.left || last == temp.right){
                    list.add(temp.val);
                    last = temp;
                    continue;
                }else{
                     if(temp.right != null){
                        stack.push(temp);
                        stack.push(temp.right);
                        
                        if(temp.left != null){
                            stack.push(temp.left);
                        }
                        continue;
                    }else{
                        if(temp.left != null){
                            stack.push(temp);
                            stack.push(temp.left);
                            continue;
                        }else{
                            list.add(temp.val);
                            last = temp;
                            continue;
                        }
                    }
                }
            }else{
                
                stack.push(temp);
                
                if(temp.right != null){
                    stack.push(temp.right);
                }
                if(temp.left != null){
                    stack.push(temp.left);
                }
                
                last = temp;
            }
            
        }
        return list;
        
    }
}
Show Comments

Get the latest posts delivered right to your inbox.