leetcode二叉树三种非递归遍历方式

110 阅读 0 评论 73 点赞

我是靠谱客的博主任性歌曲，最近开发中收集的这篇文章主要介绍leetcode二叉树三种非递归遍历方式，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树有三种深度遍历的方式，分别是前序，中序和后序，分别对应LeetCode的144，94，145三道题目。三种遍历方式的递归写法都差不多，也比较容易，相信大家都已经烂熟于心了。这里我总结了三种遍历的非递归的写法，下面分别讲三种遍历的解法：

Leetdcode 144 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>();  // 初始化栈

    TreeNode cur = root;  // cur指向当前结点

    while (cur != null || !stack.isEmpty()) {  // 循环条件：cur不为空 或者 栈不为空。 其中cur不为空的情况出现在：左节点和根节点都访问完毕时，当前指向根节点的右节点时，栈恰好为空，但是此时还未结束。
        if (cur != null) {  //当cur不为空时，先输出其值，再将其压栈（为了后面能够进入其右节点），再访问它的左节点。
            result.add(cur.val);
            stack.push(cur.right);
            cur = cur.left;
        }
        else {   //当cur为空时，弹栈。此时栈顶元素已经被访问且输出过，所以此次直接进入其右节点即可。
            cur = stack.pop();  
            cur = cur.right;
        }
    }
    return result;
}

中序遍历稍微改下就ok了，代码如下：

Leedode 94 中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>();  // 初始化栈

    TreeNode cur = root;  // cur指向当前结点

    while (cur != null || !stack.isEmpty()) {  // 循环条件：cur不为空 或者 栈不为空。 其中cur不为空的情况出现在：左节点和根节点都访问完毕时，当前指向根节点的右节点时，栈恰好为空，但是此时还未结束。
        if (cur != null) {  //当cur不为空时，将其压栈，再访问它的左节点。
            stack.push(cur.right);
            cur = cur.left;
        }
        else {   //当cur为空时，弹栈，值赋给cur。此时cur的左子树都已经访问过并且输出了，接下来应该输出cur，然后进入右子树。
            cur = stack.pop();  
            result.add(cur.val);
            cur = cur.right;
        }
    }
    return result;
}

后序遍历的非递归写法，相比于前序遍历和中序遍历，要更加困难一些。因为前序遍历和中序遍历都可以在一个循环里，分两个分支，做确定的事情即可。而后序遍历不一样，后序遍历在遇到null弹栈的时候，有两种情况，一种是从左子树回来，此时不能像中序遍历一样直接弹栈，因为根节点要留着，等把右子树也访问完毕后再输出，所以此时要直接进入右子树，待右子树都输出之后再回来的时候才能弹出根节点，因此我们要知道当前是从左子树回去还是从右子树回去。这里我们用一个集合Set来存储已经从左子树回去过的根节点，因此下次从右子树回去的时候，就知道应该输出根了。
代码如下：

leetcode 145 后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>(); // 初始化栈
    Set<TreeNode> visited = new HashSet<>(); // 初始化集合，存放已经从左子树返回过的节点。

    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {  //当cur不为空时，将其压栈，再访问它的左节点。
            stack.push(cur);
            cur = cur.left;
        }
        else {   // 当cur为空时，需要分两种情况：从左子树返回、从右子树返回。
            TreeNode tmp = stack.peek();
            if (visited.contains(tmp)) {   //visited中已经有cur了，说明从右子树返回，可以输出根了。
                result.add(tmp.val);
                stack.pop();   // 记得这里一定要将cur弹出，因为上面是用的peek
            }
            else {     // visited中没有tmp，说明第一次返回，也就是从左子树返回的，因此标记访问后，直接进入右节点。
                visited.add(tmp);
                cur = tmp.right;
            }
        }
    }
    return result;
}