二叉树的后序遍历---非递归解法(简单难度)

简介: 二叉树的后序遍历---非递归解法(简单难度)

题目概述(简单难度)

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题目链接

点我进入leetcode

思路与代码

思路展现

这道题目的思路我放到了这篇博客里,大家点击对应目录便可以查看啦:

点我进入博客

代码示例

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //注意使用peek而不是poll
            TreeNode top = stack.peek();
            //每次不但要判断右边是否为空,还要判断右子树的节点是否为上次打印过的节点
            if (top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                //定义一个prev变量,用于每次保存上次打印过的节点
                prev = top;
            } else {
                cur = top.right;
            }
        }
        return list;
    }
}

总结

非递归解法是比较难的一个解法,比递归解法繁琐,逻辑没有递归那么清晰,但是也是不错的一个解法,希望大家好好学习

相关文章
|
6月前
|
Java BI 数据库管理
二叉树---前,中,后序遍历做题技巧(前,中,后,层次,线索二叉树)
二叉树---前,中,后序遍历做题技巧(前,中,后,层次,线索二叉树)
87 11
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
48 0
|
6月前
|
存储 算法
常见的二叉树系统题解(二)
常见的二叉树系统题解(二)
|
6月前
|
存储
LeetCode题94,44,145,二叉树的前中后序遍历,非递归
LeetCode题94,44,145,二叉树的前中后序遍历,非递归
62 0
|
6月前
|
算法
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
98 0
|
6月前
|
存储 算法
常见的二叉树系统题解(一)
常见的二叉树系统题解(一)
非递归方式实现二叉树的前、中、后序遍历
非递归方式实现二叉树的前、中、后序遍历
|
存储 算法 JavaScript
算法系列-二叉树遍历(非递归实现)
在内卷潮流的席卷下,身为算法小白的我不得不问自己,是否得踏上征程,征服这座巍巍高山。 从零开始,终点不知何方,取决于自己可以坚持多久。 希望你可以和我一样,克服恐惧,哪怕毫无基础,哪怕天生愚钝,依然选择直面困难。
二叉树的中序遍历---非递归解法(简单难度)
二叉树的中序遍历---非递归解法(简单难度)
83 0
二叉树的中序遍历---非递归解法(简单难度)
二叉树的前序遍历--非递归解法(简单难度)
二叉树的前序遍历--非递归解法(简单难度)
90 0
二叉树的前序遍历--非递归解法(简单难度)