美文网首页
二叉树的前中后序的非递归遍历

二叉树的前中后序的非递归遍历

作者: abboo | 来源:发表于2021-05-13 11:01 被阅读0次

非递归前序遍历

首先我们应该创建一个Stack用来存放节点,首先我们想要打印根节点的数据,此时Stack里面的内容为空,所以我们优先将头结点加入Stack,然后打印。

之后我们应该先打印左子树,然后右子树。所以先加入Stack的就是右子树,然后左子树。
此时你能得到的流程如下:

中序遍历流程图
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<>();
        if(root == null )return res;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offerLast(root);
        while(!deque.isEmpty()){
            TreeNode node = deque.pollLast();
            res.add(node.val);
            if(node.right!=null)deque.offerLast(node.right);
            if(node.left!=null)deque.offerLast(node.left);
        }
        return res;
    }
}

方法二

每次往左子树走,走到空再去右子树,在这里模拟递归操作,就是往左子树走前加入结果集

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}

非递归中序遍历

使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。

class Solution {
    class Color{
        TreeNode node;
        boolean used;
        Color(TreeNode node){
            this.node = node;
            used = false;
        }
    }
    
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<>();
        if(root==null)return res;
        Deque<Color>deque = new ArrayDeque<>();
        Color cur = new Color(root);
        deque.offerLast(cur);
        while(!deque.isEmpty()){
            cur = deque.pollLast();
            if(cur==null)continue;
            // 节点没被访问过
            if(!cur.used){
                if(cur.node.right!=null)deque.offerLast(new Color(cur.node.right));
                cur.used = true;
                deque.offerLast(cur);
                if(cur.node.left!=null)deque.offerLast(new Color(cur.node.left));
            }
            else{
                // 节点被访问过
                res.add(cur.node.val);
            }
        }
        return res;

    }


}

方法2

同理创建一个Stack,然后按 左 中 右的顺序输出节点。
尽可能的将这个节点的左子树压入Stack,此时栈顶的元素是最左侧的元素,其目的是找到一个最小单位的子树(也就是最左侧的一个节点),并且在寻找的过程中记录了来源,才能返回上层,同时在返回上层的时候已经处理完毕左子树了。。
当处理完最小单位的子树时,返回到上层处理了中间节点。(如果把整个左中右的遍历都理解成子树的话,就是处理完 左子树->中间(就是一个节点)->右子树)
如果有右节点,其也要进行中序遍历。

中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<>();
        if(root==null)return res;
        Deque<TreeNode>deque = new ArrayDeque<>();
        TreeNode node = root;
        while(!deque.isEmpty()||node!=null){
             while(node!=null){
                 deque.offerLast(node);
                 node = node.left;
             }
             node = deque.pollLast();
             res.add(node.val);
             node = node.right;
        }
        return res;
    }
    
}

非递归后序遍历

方法1,颜色标记法

颜色标记法,根节点入栈时候一开始是(0,root),但是孩子要入栈的时候必须先变成(1,root)孩子才能入栈,如果已经执行过入栈操作,就直接输出,

class Solution {
    class Color{
        TreeNode node;
        boolean used;
        Color(TreeNode node){
            this.node = node;
            used = false;
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<>();
        if(root==null)return res;
        Deque<Color>deque = new ArrayDeque<>();
        Color cur = new Color(root);
        deque.offerLast(cur);
        while(!deque.isEmpty()){
            cur = deque.pollLast();
            if(cur==null)continue;
            // 节点没被访问过
            if(!cur.used){
                // 按照中右左的顺序入栈,出栈顺序就为左右中了
                cur.used = true;
                deque.offerLast(cur);
                if(cur.node.right!=null)deque.offerLast(new Color(cur.node.right));
                if(cur.node.left!=null)deque.offerLast(new Color(cur.node.left));
            }
            else{
                // 节点被访问过
                res.add(cur.node.val);
            }
        }
        return res;
    }
}

方法二 模拟递归的栈操作

一种思想是利用双向链表的addFirst,对外部次序和内含次序进行同时翻转,同样会得到一种非常”优雅”的解法,结构简单明晰,甚至还有点好背(狗头)。但是,它并没有真正实现“遍历”——仔细看会发现,该算法其实在使用一种异构的前序遍历:“中->右->左”,而非传统意义上的“中->左->右”,而这种异构也正是他的第一次反转。而第二次反转就在输出序列上。

所以本质上,这是一个“前序遍历”,而不是所谓的“后序遍历”。只有当你的各个节点以“左->右->中”的次序依次出现在迭代的loop当中时,它才是真正的后序遍历,就像官解那样。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            // 模拟栈的操作,一直往左走,并且将结点入栈 对应#1
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 遇到最左边的结点了,就将栈顶的结点出栈
            root = stack.pop();
            if (root.right == null || root.right == prev) { // 对应下面的#2执行完成,即将执行#3
                // 对当前结点而言,如果不用向右走,或者右边已经走过了
                // 说明到最底下了
                res.add(root.val);
                // 避免重复访问右子树[记录当前节点便于下一步对比]
                prev = root;
                // 避免重复访问左子树[设空节点]
                root = null;
            } else {// 对应下面的#1执行完成,即将执行#2
                // 对当前结点而言,如果要向右走
                // 还得保存一下,当前结点,以便之后回到当前结点
                // 保存当前结点是实现的关键
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

上面代码中else语句是这样理解的,递归版本中,先执行下面代码的#1,再执行下面代码的#2,执行#2的时候还是得保存一下当前上下文信息,直到#2也执行完了,也即一个根节点会有两次入栈的过程。

postOrder(root.left); #1
postOrder(root.right); #2
res.add(root.val); #3

对于prev指针的使用时因为模拟递归过程时候我们不知道从上一个函数返回到当前函数时候,是#1刚执行完还是#2刚执行完,prev就是指代上一个被调用的方法,也就是上一个遍历的结点

addFirst版本

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (null == root) return ans;
        stack.addFirst(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.removeFirst();
            ans.addFirst(node.val);
            if (null != node.left) {
                stack.addFirst(node.left);
            }
            if (null != node.right) {
                stack.addFirst(node.right);
            }
        }
        return ans;
    }
}

相关文章

  • 左神算法笔记——Morris遍历

    基本问题——实现二叉树的前序、中序、后序遍历 (递归、非递归,mirros方法) 递归 递归方式下的前中后遍历 非...

  • goLang 二叉树遍历(递归 非递归 前序遍历 中序遍历 后序

    goLang 二叉树遍历(递归 非递归 前序遍历 中序遍历 后序遍历 层序遍历) 前序遍历 中序遍历 后序遍历 代...

  • 二叉树遍历-JAVA实现

    基础二叉树 二叉树遍历分为前序、中序、后序递归和非递归遍历、还有层序遍历。 前序递归遍历算法:访问根结点-->递归...

  • 二叉树,非递归法

    递归法 二叉树的递归,有前序遍历、中序遍历、后序遍历,一般采用递归法,比较简单 非递归法 二叉树非递归法,采用栈来实现

  • 二叉树的操作

    /*主要内容:1、实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式*/ 实现二叉树的先序、中序、后序遍历...

  • 算法之二叉树

    二叉树之C++实现 创建二叉树 复制二叉树 先序遍历 递归实现 非递归实现 中序遍历 递归实现 非递归实现 后序遍...

  • 各种二叉树遍历

    C++实现,二叉树的递归、非递归版本的前序、中序、后序遍历。

  • 二叉树遍历

    先序遍历——[递归、非递归] 中序遍历——[递归、非递归] 后序遍历——[递归、非递归] 层次遍历——[递归、非递归]

  • 【树】 (1)Leetcode 12道二叉树基础题

    94. 二叉树的中序遍历 札记: 说一下非递归遍历前中后序遍历指的是 head节点的是“最先遍历”,还是“中间”,...

  • 递归调用中的递归序

    从刚开始接触递归,到接触二叉树递归遍历,简单几行代码就能实现前中后序遍历,而且,前中后序遍历的代码基本一致,觉得好...

网友评论

      本文标题:二叉树的前中后序的非递归遍历

      本文链接:https://www.haomeiwen.com/subject/ldmtjltx.html