首页 > 编程语言 >代码随想录算法训练营第十八天| 513. 找树左下角的值 112. 路径总和 113. 路径总和 II

代码随想录算法训练营第十八天| 513. 找树左下角的值 112. 路径总和 113. 路径总和 II

时间:2024-03-23 13:22:20浏览次数:30  
标签:node 第十八天 val sum 路径 left path null 总和

513. 找树左下角的值
https://leetcode.cn/problems/find-bottom-left-tree-value/description/

public int findBottomLeftValue(TreeNode root) {
        int val = 0;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.poll();
                if (i == 0) val = node.val;
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
        }
        return val;
    }

总结:层序遍历
112. 路径总和
https://leetcode.cn/problems/path-sum/description/

public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        boolean sum = sum(root, targetSum);
        return sum;
    }
    public boolean sum(TreeNode node,int sum){
        if (node.left == null && node.right == null) {
            return sum - node.val == 0; // 到达叶子节点时判断路径和是否等于目标和
        }
        boolean sumLeft = false;
        boolean sumRight = false;
        if (node.left != null) {
            sumLeft = sum(node.left, sum - node.val);
        }
        if (node.right != null){
            sumRight = sum(node.right, sum - node.val);
        }
        return sumLeft || sumRight;
    }

总结:递归到叶子节点,判断是否合理
113. 路径总和 II
https://leetcode.cn/problems/path-sum-ii/description/

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> resList = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (root == null) return resList;
        pathSSum(root,targetSum,resList,path);
        return resList;
    }
    public void pathSSum(TreeNode node,int targetSum,List<List<Integer>> resList,List<Integer> path){
        if (node.left == null && node.right == null){
            if (targetSum - node.val == 0){
                path.add(node.val);
                resList.add(new ArrayList<>(path));
                path.remove(path.size() - 1); //回溯
            }
            return;
        }
        if (node.left != null){
            path.add(node.val);
            pathSSum(node.left,targetSum - node.val,resList,path);
            path.remove(path.size() - 1); //回溯
        }
        if (node.right != null){
            path.add(node.val);
            pathSSum(node.right,targetSum - node.val,resList,path);
            path.remove(path.size() - 1); //回溯
        }
    }

总结:带了点回溯

标签:node,第十八天,val,sum,路径,left,path,null,总和
From: https://www.cnblogs.com/jeasonGo/p/18091010

相关文章

  • 【VRP问题】基于粒子群算法求解带时间窗的路径最短多车辆多任务车辆路径规划CTWVRP问
     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 机器人路径规划:基于霸王龙优化算法(Tyrannosaurus optimization,TROA)的机器人路径规划(提
     一、机器人路径规划介绍移动机器人(Mobilerobot,MR)的路径规划是移动机器人研究的重要分支之,是对其进行控制的基础。根据环境信息的已知程度不同,路径规划分为基于环境信息已知的全局路径规划和基于环境信息未知或局部已知的局部路径规划。随着科技的快速发展以及机器人的大量......
  • 解读国内首家AI Agent公测背后的商业落地路径
    随着大语言模型技术的日益成熟,国内科技巨头纷纷加快在AI Agent领域的布局和应用落地。凭借自身强大的技术积累和丰富的应用场景,推动AI Agent技术在各行各业的深度融合与创新应用。在AI Agent的落地应用上,目前科技巨头正借助已有AI技术平台集体发力,众多创业公司也在拼命......
  • 解读国内首家AI Agent公测背后的商业落地路径
     随着大语言模型技术的日益成熟,国内科技巨头纷纷加快在AIAgent领域的布局和应用落地。凭借自身强大的技术积累和丰富的应用场景,推动AIAgent技术在各行各业的深度融合与创新应用。在AIAgent的落地应用上,目前科技巨头正借助已有AI技术平台集体发力,众多创业公司也在拼命迎头......
  • 1.基于搜索的路径规划:BFS、DFS、Dijkstra、A*、JPS
    1.概览可以对比不同算法的小动画 PathFinding.js(qiao.github.io)工作空间规划机器人有不同的形状和大小碰撞检测需要了解机器人的几何形状,耗时且难度大 我们希望将机器人表示为点,只需要把工作空间转换为配置空间C-obstacle,将原始的空间膨胀,这是一次性的C-space......
  • IDEA项目路径初探
    IDEA项目路径初探:https://blog.csdn.net/qq_30591155/article/details/109046394?ops_request_misc=&request_id=&biz_id=102&utm_term=idea%20java%20%E7%89%88%E6%9C%AC%E7%9A%84%E9%A1%B9%E7%9B%AE%E7%9B%AE%E5%BD%95&utm_medium=distribute.pc_search_result.n......
  • js 如何提取富文本里的图片路径
    在JavaScript中,要从富文本内容中提取图片路径,你可以创建一个DOM元素来作为解析富文本内容的容器,然后将富文本内容作为文本节点插入这个容器中。接着,你可以使用querySelectorAll方法和CSS选择器来选择所有的img元素,并获取它们的src属性。以下是一个简单的示例代码functionextra......
  • 代码随想录算法训练营第十七天| 110. 平衡二叉树 257. 二叉树的所有路径 404. 左叶
    110.平衡二叉树https://leetcode.cn/problems/balanced-binary-tree/description/publicbooleanisBalanced(TreeNoderoot){intbalance=balance(root);returnbalance==-1?false:true;}publicintbalance(TreeNodenode){i......
  • (44/60)完全背包、零钱兑换Ⅱ、组合总和Ⅳ
    day44完全背包卡码网:携带研究材料(第七期模拟笔试)动态规划思路完全背包,物品可以无限次取,正序遍历。复杂度分析时间复杂度:O(N^2)。空间复杂度:O(N)。代码实现#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;/*给j的容量可重复选择的最......
  • leetcode 路经总和 pathsum
    很熟悉的一道题,XX二面做过,面试官没让我当场造树,让我用数组模拟树来运行,依旧跑出来了。但是刚刚再做了一下,没思路,不会写......