【leetcode】第六章 二叉树part01

这篇具有很好参考价值的文章主要介绍了【leetcode】第六章 二叉树part01。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

递归遍历

144. 二叉树的前序遍历

// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }

    private void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }

94. 二叉树的中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
        // 递归
        List<Integer> res = new ArrayList<>();
        inOrder(root, res);
        return res;
    }

    private void inOrder(TreeNode root, List<Integer> res) {
        if (root == null) return;

        inOrder(root.left, res);
        res.add(root.val);
        inOrder(root.right, res);
    }

145. 二叉树的后序遍历文章来源地址https://www.toymoban.com/news/detail-680538.html

public List<Integer> postorderTraversal(TreeNode root) {
        // 递归
        List<Integer> res = new ArrayList<>();
        postOrder(root, res);
        return res;

    }

    private void postOrder(TreeNode root, List<Integer> res) {
        if (root == null) return;

        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);

    }

非递归遍历

  • 前序
public List<Integer> preorderTraversal(TreeNode root) {
        // 非递归
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 一直将左节点压入栈中
            while (root != null) {
                res.add(root.val); // 根节点首先访问
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right; 
        }

        return res;
    }
  • 中序
public List<Integer> inorderTraversal(TreeNode root) {
        // 非递归
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
  • 后序
public List<Integer> postorderTraversal(TreeNode root) {
    // 非递归
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    while (root != null || !stack.isEmpty()) {
        // 将左节点压入栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        // 后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。
        // 所以当前不管是从左子树还是右子树回到根结点都不应该再 操作了,应该退回上层。
        // 如果是从右边再返回根结点,应该回到上层。
        // 主要就是判断出来的是不是右子树,是的话就可以把根节点=加入到list了
        if (root.right == null || root.right == prev) {
            res.add(root.val);
            prev = root;
            root = null;
        }
        else {
            stack.push(root);
            root = root.right;
        }

    }

    return res;

}

到了这里,关于【leetcode】第六章 二叉树part01的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcoder Day12| 二叉树 part02

    语言:Java/C++  给你一个二叉树,请你返回其按层序遍历得到的节点值。 (即逐层地,从左到右访问所有节点)。 在昨天的二叉树理论基础里有提到,层序遍历需要借助队列实现。 队列先进先出,符合一层一层遍历的逻辑 这里要注意的是,定义每一层元素列表的时候ListIn

    2024年01月20日
    浏览(37)
  • Leetcoder Day16| 二叉树 part05

    语言:Java/C++  给定一个二叉树的  根节点   root ,请找出该二叉树的  最底层 最左边  节点的值。 假设二叉树中至少有一个节点。 示例 1: 示例 2: 本题需要满足两个条件:(1) 最后一行的 (2) 最左边的值 。 这里需要明白一个概念是,最左边的值未必就是左孩子,右孩

    2024年02月21日
    浏览(31)
  • leetcode刷题(9)二叉树(3)

    各位朋友们,提前祝大家五一劳动节快乐啊!!!今天我为大家分享的是关于leetcode刷题二叉树相关的第三篇我文章,让我们一起来看看吧。 leetcode之二叉树的层序遍历(难度:中等) 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节

    2023年04月26日
    浏览(31)
  • leetcode刷题(10)二叉树(4)

    各位朋友们,大家五一劳动节快乐啊,在这里祝大家假期玩得愉快!但是在玩耍的期间不要忘记了敲代码哦。今天我为大家分享的是二叉树的第四篇,废话不多说,我们一起来看看吧。 leetcode之二叉树的最近公共祖先(难度:中等) 给定一个二叉树, 找到该树中两个指定节点

    2024年02月02日
    浏览(34)
  • leetcode刷题(8)二叉树(2)

    各位朋友们,大家好!今天我为大家分享的是关于二叉树leetcode刷题的第二篇,我们一起来看看吧。 leetcode之对称二叉树(难度:简单) 给你一个二叉树的根节点 root , 检查它是否轴对称。 输入:root = [1,2,2,3,4,4,3] 输出:true 这道题我们需要先判断二叉树的左子树的结构与右

    2023年04月24日
    浏览(30)
  • leetcode刷题(7)二叉树(1)

    哈喽大家好,这是我leetcode刷题的第七篇,这两天我将更新leetcode上关于二叉树方面的题目,如果大家对这方面感兴趣的话,欢迎大家持续关注,谢谢大家。 那么我们就进入今天的主题。 leetcode之二叉树的前序遍历(难度:简单) 给你二叉树的根节点 root ,返回它节点值的

    2023年04月25日
    浏览(32)
  • 第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

    - LeetCode 链接 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。 修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案

    2024年02月05日
    浏览(37)
  • LeetCode刷题——617. 合并二叉树

    给你两棵二叉树: root1 和 root2 。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为

    2024年02月13日
    浏览(43)
  • LeetCode刷题--- 二叉树的所有路径

    个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题       【     】 【C++】                  【   】 数据结构与算法       【    】 前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的

    2024年01月19日
    浏览(41)
  • leetcode刷题记录:二叉树02(思路篇)

    参考labuladong的算法小抄:https://labuladong.online/algo/data-structure/binary-tree-part1/ 复习二叉树纲领篇,二叉树解题的思维模式分两类: 1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。 2、是否可以定义一个

    2024年02月19日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包