Java 后序遍历非递归实现

ymyang 发布于2019-08-16 12:42 / 1195人阅读

摘要：今天刷后序遍历非递归实现时，因为以前看过借助一个栈和队列来实现，但始终模糊不清，不知道如何写，只好自己捋了一遍，然后查了下，发现和很多人写法有差异，故放出来，欢迎指正，如有知道用栈和队列方式实现的朋友，也请赐教。

今天刷后序遍历非递归实现时，因为以前看过借助一个栈和队列来实现，但始终模糊不清，不知道如何写，只好自己捋了一遍，然后查了下，发现和很多人写法有差异，故放出来，欢迎指正，如有知道用栈和队列方式实现的朋友，也请赐教。

    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList result = new ArrayList<>();
        if(root==null){
            return result;
        }
        TreeNode node = root;
        Stack stack = new Stack<>();
        Stack markStack = new Stack<>();
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            
            while(!markStack.isEmpty()&&markStack.peek()==stack.peek()){
                  markStack.pop();;
                  result.add(stack.pop().val);
            }
            if(!stack.isEmpty()){
                node = stack.peek();
                markStack.push(node);
                node = node.right;
            }
        }
        
        
        return result;
    }

海外云主机私有云非递归遍历非递归二叉树遍历递归遍历java 后序遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71564.html

【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

ghnor 2019-08-23 16:19 评论0 收藏0
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

FuisonDesign 2019-08-16 16:04 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
二叉树遍历

摘要：前言本篇文章是在二叉排序树的基础上进行遍历查找与删除结点。接下来我们根据构造的这颗二叉树进行相应遍历查找与删除操作。遍历二叉树二叉树的遍历分为深度优先遍历和广度优先遍历。中序遍历二叉排序树，得到的数组是有序的且是升序的。前言本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。那么首先来看一下什么是二叉排序树？二叉排序树定义二叉排序树，又称二叉查找树、二叉搜索树。若...

aboutU 2019-08-26 13:54 评论0 收藏0