首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:路径总和

#yyds干货盘点# LeetCode程序员面试金典:路径总和

时间:2023-05-24 23:32:04浏览次数:48  
标签:yyds null offer queNode 金典 LeetCode now root 节点

题目:

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

 

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出:true

解释:等于目标和的根节点到叶节点路径如上图所示。

示例 2:

输入:root = [1,2,3], targetSum = 5

输出:false

解释:树中存在两条根节点到叶子节点的路径:

(1 --> 2): 和为 3

(1 --> 3): 和为 4

不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:

输入:root = [], targetSum = 0

输出:false

解释:由于树是空的,所以不存在根节点到叶子节点的路径。

代码实现:

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }
}

标签:yyds,null,offer,queNode,金典,LeetCode,now,root,节点
From: https://blog.51cto.com/u_13321676/6343478

相关文章

  • #yyds干货盘点# LeetCode程序员面试金典:Excel表列名称
    1.简述:给你一个整数 columnNumber,返回它在Excel表中相对应的列名称。例如:A->1B->2C->3...Z->26AA->27AB->28... 示例1:输入:columnNumber=1输出:"A"示例2:输入:columnNumber=28输出:"AB"示例3:输入:columnNumber=701输出:"ZY"示例4:输入:colum......
  • 每日一题 力扣 1377 https://leetcode.cn/problems/frog-position-after-t-seconds/
    力扣1377https://leetcode.cn/problems/frog-position-after-t-seconds/这道题目用dp去做,构建邻接矩阵,做的时候需要注意题目条件,如果青蛙跳不动了,这个概率就保持不变了一般跳青蛙,很容易想到dp核心代码如下publicdoublefrogPosition(ipublicdoublefrogPosition(intn,......
  • LeetCode 98. 验证二叉搜索树
    classSolution{public:vector<int>dfs(TreeNode*root)//依次返回是否是二叉搜索树,最大值最小值{vector<int>res{1,root->val,root->val};if(root->left){autol=dfs(root->left);res[1]=max(res......
  • LeetCode 222. 完全二叉树的节点个数
    classSolution{public:intcountNodes(TreeNode*root){if(!root)return0;autol=root->left,r=root->right;intx=1,y=1;//记录左右两边层数while(l)l=l->left,x++;while(r)r=r->right,y++;......
  • 二刷Leetcode-Days07
    动规:/***70.爬楼梯*@paramn*@return*/publicintclimbStairs(intn){if(n<=2){returnn;}int[]dp=newint[n];dp[0]=1;dp[1]=2;for(inti=2;i......
  • Linux 常用命令大全【yyds干货盘点1】
    1. 系统信息arch显示机器的处理器架构(1)uname-m显示机器的处理器架构(2)uname-r显示正在使用的内核版本dmidecode-q显示硬件系统部件-(SMBIOS/DMI)hdparm-i/dev/hda罗列一个磁盘的架构特性hdparm-tT/dev/sda在磁盘上执行测试性读取操作cat/proc/cp......
  • #yyds干货盘点#JavaScript的数学对象——Math对象
    Math对象●js给我们提供了一些操作数字的方法●也是一种数据类型是复杂数据类型●Math对象的通用语法:Math.xxx()random()●Math.random()这个方法是用来生成一个0~1之间的随机数●每次执行生成的数字都不一样,但是一定是0~1之间的●生成的数字包含0,但是不包含1var......
  • LeetCode 62.不同路径
    1.题目:一个机器人位于一个mxn 网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?示例1:输入:m=3,n=7输出:28来源:力扣(LeetCode)链接:https://leetcode.c......
  • leetcode2215哈希列表的应用
    哈希列表存储的是不重复的元素,使用两个哈希列表存储这两个数组。再遍历其中一个哈希列表,查看是否存在另一个哈希列表中set.insert()set1.count(元素)for(intnum:nums1){set1.insert(num);}for(intnum:set1){if(!set2.count(num)){res[0].push_back(num);......
  • bst中序-leetcode230二叉搜索树第k个元素
    给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从1开始计数)。示例1:输入:root=[3,1,4,null,2],k=1输出:1示例2:输入:root=[5,3,6,2,4,null,null,1],k=3输出:3提示:树中的节点数为 n 。1<=k<=n<=1040<=Node.val<......