二叉树的后序遍历（递归和非递归）

川长思鸟来 2022-06-06 01:12 212阅读 0赞

对于二叉树的后序遍历，最常用的就是递归，代码清晰，如下：

ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<Integer> postorderTraversal(TreeNode root) {
    
            if(root == null)
                return list;
            sort(root);
            return list;
    
        }
        private void sort(TreeNode root){
            if(root == null)
                return;
            sort(root.left);
            sort(root.right);
            list.add(root.val);
        }

但是当二叉树高度很大的时候，递归就容易导致栈溢出，所以就需要将递归改为非递归方式，代码如下：

public ArrayList<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if(root == null)
                return list;
            Stack<TreeNode> s = new Stack<>();
            TreeNode p = root;
            TreeNode r = null;//用来记录上次被访问的节点
            while(p != null || !s.isEmpty()){
                if(p != null){
                    s.push(p);
                    p = p.left;
                }else{
                    p = s.peek();
                    p = p.right;
                    if(p != null && p != r){
                        s.push(p);
                        p = p.left;
                    }else{
                        p = s.pop();
                        list.add(p.val);
                        r = p;
                        p = null;
                    }
                }
            }
            return list;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树后序遍历(非递归)

叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代...

深藏阁楼爱情的钟/ 2024年04月17日 22:41/ 0 赞/ 10 阅读

相关二叉树后序遍历 -- 递归和非递归实现

/实现二叉树后序遍历 -- 采用递归和非递归方法经调试可直接运行源码如下： / include <stdio.h> incl

刺骨的言语ヽ痛彻心扉/ 2022年07月28日 08:59/ 0 赞/ 130 阅读

相关二叉树的前序遍历（递归和非递归）

上一篇是后续遍历，这一篇记录一下前序遍历，递归代码如下： ArrayList<Integer> list = new ArrayList<>(); p

Bertha 。/ 2022年06月06日 01:14/ 0 赞/ 143 阅读

相关二叉树的后序遍历（递归和非递归）

对于二叉树的后序遍历，最常用的就是递归，代码清晰，如下： ArrayList<Integer> list = new ArrayList<>(); p

川长思鸟来/ 2022年06月06日 01:12/ 0 赞/ 213 阅读

相关二叉树的非递归后序遍历

![70][] import java.util.; class TreeNode { int val; TreeNo

小灰灰/ 2022年05月23日 02:59/ 0 赞/ 135 阅读

相关二叉树的先序、中序、后序递归和非递归遍历

二叉树遍历总结 import java.util.Stack; / 二叉树的遍历 @author superman / public cla

绝地灬酷狼/ 2022年05月15日 02:43/ 0 赞/ 177 阅读

相关二叉树的后序遍历（递归和非递归版本）

难易程度：★★ 重要性：★★★★★ 树结构是面试中的考察的重点，而树的遍历又是树结构的基础。非递归的前序遍历算法思路可以借鉴。 / 后序遍历

矫情吗；*/ 2022年05月09日 05:44/ 0 赞/ 129 阅读

相关二叉树的后序遍历（递归与非递归）

二叉树后序遍历介绍了二叉树的先序以及中序遍历，那么我简单的再给大家介绍了一下二叉树的后序遍历。请看大屏幕。。。。 ![在这里插入图片描述][watermark

ゝ一世哀愁。/ 2022年04月24日 07:54/ 0 赞/ 137 阅读

相关非递归、递归遍历二叉树！

树的先、中、后、层序的遍历，需要用到栈结构和队结构。首先来看树本身的定义： typedef char TElemType; typedef struct BiTNod

小鱼儿/ 2022年04月13日 10:29/ 0 赞/ 288 阅读

相关二叉树递归和非递归遍历

二叉树递归和非递归遍历 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

拼搏现实的明天。/ 2021年12月17日 04:07/ 0 赞/ 299 阅读