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

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

题目概述(简单难度)

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

示例:

输入: [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月前
|
索引
leetcode106从中序与后序遍历序列构造二叉树刷题打卡
leetcode106从中序与后序遍历序列构造二叉树刷题打卡
35 0
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
47 0
|
6月前
|
算法
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
88 0
|
算法
剑指offer_二叉树---平衡二叉树
剑指offer_二叉树---平衡二叉树
69 0
剑指offer_二叉树---二叉搜索树的后序遍历
剑指offer_二叉树---二叉搜索树的后序遍历
68 0
非递归方式实现二叉树的前、中、后序遍历
非递归方式实现二叉树的前、中、后序遍历
二叉树的中序遍历---非递归解法(简单难度)
二叉树的中序遍历---非递归解法(简单难度)
82 0
二叉树的中序遍历---非递归解法(简单难度)
二叉树的中序遍历---递归解法(简单难度)
二叉树的中序遍历---递归解法(简单难度)
93 0
二叉树的中序遍历---递归解法(简单难度)
二叉树的前序遍历---递归解法(简单难度)
二叉树的前序遍历---递归解法(简单难度)
85 0
二叉树的前序遍历---递归解法(简单难度)
二叉树的前序遍历--非递归解法(简单难度)
二叉树的前序遍历--非递归解法(简单难度)
90 0
二叉树的前序遍历--非递归解法(简单难度)