LeetCode题94,44,145,二叉树的前中后序遍历,非递归

简介: LeetCode题94,44,145,二叉树的前中后序遍历,非递归

注意:解题都要用到栈

一、前序遍历

题目要求

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入:root = [1,null,2,3]

输出:[1,2,3]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]


示例 4:

输入:root = [1,2]

输出:[1,2]


示例 5:

输入:root = [1,null,2]

输出:[1,2]

解题思路

我们想要用非递归的方式进行前序遍历,那么我们可以用到栈

因为遍历的值要放在链表里,所以我们先存放根节点的值,同时当前节点要放进栈里,存放完后再往左边遍历

每往左边遍历一次都要把当前根节点的值放进链表里,同时当前节点也要放进栈里

直到roo.left == null,我们就要找前一个节点的右子树为不为null,因为我们已经用栈进行存储了,所以我们可以找到前一个节点,pop一下,拿到前一个节点,再判断右子树为不为空,然后一直往回走,上述步骤,直到根节点,去判断根节点的右子树,然后也是重复上面的步骤。

代码展示

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()) {
            while(root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }

二、中序遍历

题目要求

给定一个二叉树的根节点 root ,返回 它的 中序 遍历

示例 1:

输入:root = [1,null,2,3]

输出:[1,3,2]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]

解题思路

想要用非递归的思路进行中序遍历,其实步骤和前序遍历差不多

如图:

我们要先往左边找,一直找到头,同时,每遍历一个节点也要把这个节点放进栈里

直到左边节点为空,如图:

然后开始存入链表中,存入完返回上一个节点,也要存进链表中,判断该节点的右边是否为空,为空就不往右边遍历,不为空就往右边遍历,找是否又有左子树,又开始了上面的循环

,回到根节点就不说了,都是上面的这种循环。

代码展示:

public List<Integer> inorderTraversal(TreeNode root) {
        //非递归
        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }

三、后续遍历

题目要求

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例 1:

输入:root = [1,null,2,3]

输出:[3,2,1]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]

解题思路

后续遍历和前面的遍历都差不多,不过因为后序遍历的顺序是左右根,我们添加完左节点后,要判断有没有右节点,这时就不能直接弹出上一个根节点了,如果上一个节点有右节点,我们就要把这个根节点重新压栈,再去遍历右边的节点,等右边没有节点了,才开始把这个根节点存到链表中。

所以我们多定义一个前一个遍历的节点,判断右节点有没有遍历过,如果遍历过,我们就直接出栈这个节点,没有遍历过我们就要压栈这个节点,去遍历右边的节点。

代码展示

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prevAccess = null;
        while(root != null || !stack.empty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == prevAccess) {
                list.add(root.val);
                prevAccess = root;
                root = null;
            }else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
相关文章
|
6天前
|
算法 DataX
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
|
8天前
|
算法
【力扣】94. 二叉树的中序遍历、144. 二叉树的前序遍历、145. 二叉树的后序遍历
【力扣】94. 二叉树的中序遍历、144. 二叉树的前序遍历、145. 二叉树的后序遍历
|
1月前
leetcode热题100.二叉树中的最大路径和
leetcode热题100.二叉树中的最大路径和
18 0
|
1月前
leetcode热题100. 二叉树的最近公共祖先
leetcode热题100. 二叉树的最近公共祖先
20 0
|
26天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记
|
1月前
|
搜索推荐
《LeetCode》——LeetCode刷题日记3
《LeetCode》——LeetCode刷题日记3
|
1月前
|
容器
《LeetCode》——LeetCode刷题日记1
《LeetCode》——LeetCode刷题日记1
|
1月前
|
算法 测试技术
LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)
LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)
|
1月前
|
存储
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
143 38

热门文章

最新文章