原题
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解法
思想
DFS搜索，每经过一个节点减去对应节点的值，到叶子节点的时候查看是否为0。
代码
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
int left = sum-root.val;
if(left == 0 && root.left==null && root.right == null) return true;
return hasPathSum(root.left,left)||hasPathSum(root.right,left);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode112-%e8%b7%af%e5%be%84%e6%80%bb%e5%92%8c/
相关推荐
-
leetcode744-寻找比目标字母大的最小字母
原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子，如果目标字母tar...
-
leetcode219-存在重复元素II
原题 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。 示例1...
-
程序员面试金典08.11-硬币
原题（来源Leetcode） 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007) 示...
-
leetcode23-合并K个排序链表
原题 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入： [ 1->4->5, 1->3->4, 2->6 ] 输出： 1->1->2->3->...
-
leetcode498-对角线遍历
这是一个Z字形编排问题，JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下...
-
leetcode202-快乐数
原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无...
-
leetcode85-最大矩形
原题 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例： 输入: [ ["1","0","1","0","0"...
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
剑指offer45-把数组排成最小的数
原题（来源Leetcode） 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" ...
-
leetcode154-寻找旋转排序数组中的最小值II
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。...
