代码编织梦想


上一篇文章:【力扣刷题】Day17——二叉树专题_塔塔开!!!的博客-CSDN博客

13. 找树左下角的值

题目链接:513. 找树左下角的值 - 力扣(LeetCode)

被题目搞晕了:左下角的值并不是值左叶子节点!!!!

思路:

深度优先搜索:按照先左后右的顺序遍历子树,最先搜索到的最深的结点即所求的结点(更新深度判断即可)

class Solution {
    int res = 0;
    int max_h = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return res;
    }
    public void dfs(TreeNode root, int depth){
        if(root == null){
            return ;
        }
        
        // 遍历的第一个最深的叶子节点肯定就是最底层的最左节点(前序遍历嘛)
        if(root.left == null && root.right == null){
            // 证明是当前深度的最左边叶子节点,因为先递归左子树
            if(depth > max_h){
                res = root.val;
                max_h = depth;
            }

            if(root.left != null)
                dfs(root.left, depth + 1);
            if(root.right != null)
                dfs(root.right, depth + 1);    
        }
    }
}

14. 路径总和I

题目链接:112. 路径总和 - 力扣(LeetCode)

思路:dfs从根节点遍历到叶子节点,判断这条路径是否符合要求即可。

Code

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, targetSum);
    }
    public boolean dfs(TreeNode root, int targetSum){
        if(root == null){
            return false;
        }
        // 到达叶子节点,判断这条路径是否符合要求
        if(root.left == null && root.right == null){
            return targetSum - root.val == 0;
        }
        return dfs(root.left, targetSum - root.val) || dfs(root.right, targetSum - root.val);
    }
}

15. 路径总和II

题目链接:113. 路径总和 II - 力扣(LeetCode)

DFS:爆搜版,每一条完整的路径都要新建一个tmp_list来记录,最终(叶子节点且满足条件)在存入res————不用回溯

缺点:时间费在大量创建tmp_list上!

Code

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum, new ArrayList<>());
        return result;
    }
    public void dfs(TreeNode root, int sum, List<Integer> list) {
        //如果节点为空直接返回
        if (root == null){
            return;
        }
        sum -= root.val;
        //因为list是引用传递,为了防止递归的时候分支污染,我们要在每个路径
        //每一条完整的路径对应一个tmp
        //中都要新建一个(subList)tmp(在上一次tmp的基础上)
        List<Integer> tmp = new ArrayList(list);
        tmp.add(root.val);
        
        if (root.left == null && root.right == null && sum == 0) {
            result.add(tmp);
            return;
        }

        dfs(root.left, sum, tmp);
        dfs(root.right, sum, tmp);
    }
}

回溯版:这里之所以要回溯,那是因为我们始终在用一个list集合在记录res,当到达满足条件的叶子节点时,将本次路径重新new 出来加入res而已,为此就要回溯(弹出本次选中的末尾元素),为下一个路径做好准备!

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

    public void dfs(TreeNode root, int sum){
        if(root == null){
            return ;
        }
        sum -= root.val;// 选值

        // 到达叶子节点
        if(root.left == null && root.right == null && sum == 0){
            list.add(root.val);
            res.add(new ArrayList(list));
            list.remove(list.size() - 1);// 要是在递归出口中加入叶子节点,最后一定要弹出(回溯!!!)
            return ;
        }

        // 左 右
        list.add(root.val);
        dfs(root.left, sum);
        dfs(root.right, sum);
        list.remove(list.size() - 1);// 回溯

    }
}

16. 路径总和III

题目链接:437. 路径总和 III - 力扣(LeetCode)

双重DFS:我们遍历每一个节点,从这个节点开始计算它的子树满足要求的路径。

我们访问每一个节点 node,检测以node 为起始节点(头节点)且向下延深的路径有多少种(第二次dfs判断左右子树是否右满足的情况)。我们递归遍历每一个节点的所有可能的路径,然后将这些路径数目加起来即为返回结果。

Code

class Solution {
    int res = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        long longTargetSum = targetSum;
        dfs(root, longTargetSum);// 每一个根节点都要dfs判断
        // 为下一次dfs做好准备
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return res;
    }
    public void dfs(TreeNode root, long sum){
        if(root == null){
            return ;
        }
        sum -= root.val;
        if(sum == 0){
            rse ++;
            // 这里不能return !! 下面可能还要答案集
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
}

17. 从中序与后序遍历序列构造二叉树

题目链接:106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

具体思路回顾之前的博客:二叉树的遍历_塔塔开!!!的博客-CSDN博客_二叉树遍历

Code

class Solution {
    // 将中序的值对应位置记下,方便后面找到中序跟所在位置
    Map<Integer, Integer> pos = new HashMap<>();
    int hou[];
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        hou = postorder;
        for(int i = 0; i < n; i ++) pos.put(inorder[i], i);

        TreeNode root = build(0, n - 1, 0, n - 1);
        return root;
    }
    /**
        由中和后序构造二叉树
        build:返回二叉树的根节点
     */
    public TreeNode build(int il, int ir, int pl, int pr){
        if(il > ir || pl > pr) return null;

        int root = hou[pr];
        int k = pos.get(root);
        int x = k - 1 - il + pl;

        // 递归创建左右子树
        TreeNode node = new TreeNode(root);
        node.left = build(il, k - 1, pl, x);
        node.right = build(k + 1, ir, x + 1, pr - 1);

        return node;

    }
}

18. 从前序与中序遍历序列构造二叉树

题目链接:105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

思路:看上一题即可

Code

class Solution {
    Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
    int[] qian;
    public TreeNode buildTree(int[] pre, int[] in) {
        int n = pre.length;
        qian = pre;
        for(int i = 0; i < n; i ++) mp.put(in[i], i);
        return build(0, n - 1, 0, n - 1);
    }
    public TreeNode build(int pl, int pr, int il, int ir){
        if(pl > pr || il > ir) return null;

        int root = qian[pl];
        int k = mp.get(root);
        TreeNode node = new TreeNode(root);
        int x = k - 1 - il + pl + 1;

        node.left = build(pl + 1, x, il, k - 1);
        node.right = build(x + 1, pr, k + 1, ir);
        return node;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_54773252/article/details/127205583

【java设计模式】组合模式_beststone1的博客-爱代码爱编程

转自:  https://blog.csdn.net/qq_42322103/article/details/95457321 漫谈网站优化提速: https://blog.csdn.net/meteor_93/article/details/95518164 十分钟教你理解TypeScript中的泛型: https://blog.csdn.net/p

小记——一次刷题的错误归纳及总结(有序链表转换二叉搜索树)-爱代码爱编程

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树

Day10-2021.1.18-剑指二叉树题型整理+虚拟机。-爱代码爱编程

2021年1月18日 时间都去哪了? 今日计划: 1.剑指offer的另外八道二叉树题目的整理。操作系统/计网面经?项目呢?啊… 今日工作: 剑指 Offer 33 .二叉搜索树的后序遍历序列 剑指 Offer 34 .二叉树中和为某一值的路径 剑指 Offer 36 .二叉搜索树与双向链表 10点做累了。换其他的思路, 剑指

leecode刷题笔记——数据结构(一)-爱代码爱编程

数组 217. Contains Duplicate 存在相同元素 Given an integer array n u m s

每日刷题 Day11-爱代码爱编程

题一:二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [1,2,3,null,5] 输出:[“1->2->5”,“1->3”] 示例 2: 输入:root = [1] 输出:[“1”] 提示: 树中节点的数目在

2022-03-10每日刷题打卡-爱代码爱编程

2022-03-10每日刷题打卡 力扣——每日一题 589. N 叉树的前序遍历 给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。 示例 1: 输入:root = [1,null,3,2,4,null,5,6] 输出:[1,3

C++后端开发学习日记(第二周)-爱代码爱编程

第二周(4.11-4.15) 2022.04.11 day5 菜鸟教程之面向对象部分(很重要,常看常新) 类成员函数 类的成员函数是指那些把定义和原型写在类定义内部的函数,就像类定义中的其他变量一样。类成员函数是类的一个成员,它可以操作类的任意对象,可以访问对象中的所有成员。必须使用成员函数来访问类的成员,而不是直接访问这些类的成员。 成员函数可

新星计划Day7【数据结构与算法】 栈Part1-爱代码爱编程

新星计划Day7【数据结构与算法】 栈Part1 👩‍💻博客主页:京与旧铺的博客主页 ✨欢迎关注🖱点赞🎀收藏⭐留言✒ 🔮本文由京与旧铺原创,csdn首发! 😘系列专栏:java学习 👕参考网课:尚硅谷 💻首发时间:🎞2022年5月1日🎠 🎨你做三四月的事,八九月就会有答案,一起加油吧 🀄如果觉得博主的文章还不错的话,请三

【leetcode】精选算法top200道(二)_lynn_dai的博客-爱代码爱编程

二、中等 339、嵌套列表权重和 给定一个嵌套的整数列表 nestedList ,每个元素要么是整数,要么是列表。同时,列表中元素同样也可以是整数或者是另一个列表。 整数的 深度 是其在列表内部的嵌套层数。例如,嵌套列

【力扣刷题】day14——二叉树专题_塔塔开!!!的博客-爱代码爱编程

文章目录 二叉树的介绍二叉树的遍历1. 递归实现前序遍历中序遍历后序遍历2. 迭代实现前序遍历后序遍历中序遍历 二叉树的介绍 许多概念可以看之前的博客: 二叉树的遍历_塔塔开!!!的博客-

【力扣刷题】day15——二叉树专题_塔塔开!!!的博客-爱代码爱编程

文章目录 3. 层序遍历二叉树4. 翻转二叉树5. 对称二叉树 上一篇文章: 【力扣刷题】Day14——二叉树专题_塔塔开!!!的博客-CSDN博客 3. 层序遍历二叉树 题目链接:102

【力扣刷题】day17——二叉树专题_塔塔开!!!的博客-爱代码爱编程

文章目录 10. 平衡二叉树11. 二叉树的所有路径12. 左叶子之和 上一篇文章:【力扣刷题】Day16——二叉树专题_塔塔开!!!的博客-CSDN博客 10. 平衡二叉树 题目链接:1

【力扣刷题】day16——二叉树专题_塔塔开!!!的博客-爱代码爱编程

文章目录 6. 二叉树的最大深度8. 二叉树的最小深度7. N 叉树的最大深度9. 完全二叉树的节点个数 上一篇文章:【力扣刷题】Day15——二叉树专题_塔塔开!!!的博客-CSDN博客

【力扣刷题】day19——二叉树专题_塔塔开!!!的博客-爱代码爱编程

文章目录 19. 最大二叉树20. 合并二叉树21二叉搜索树中的搜索22.验证二叉搜索树 上一篇文章:【力扣刷题】Day18——二叉树专题_塔塔开!!!的博客-CSDN博客 19. 最大二叉

力扣&pta~每天至少三题_力扣每日打卡三题在哪里-爱代码爱编程

文章目录 算法双指针平方数之和167.两数之和-输入有序数组Reverse Vowels of a string 二分法153. Find Minimum in Rotated Sorted Array

力扣刷题——剑指offer(第二版)|| java语言|| day2[重建二叉树,用两个栈实现队列]-爱代码爱编程

目录   1.重建二叉树 【题目】  【思路】  【代码】  2.用两个栈实现队列 【题目】  【思路】  【代码】   1.重建二叉树 【题目】     输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。   In