LeetCode 「简单」112.路径总和
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点是指没有子节点的节点。
示例
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
输入：root = [1,2,3], targetSum = 5
输出：false
输入：root = [], targetSum = 0
输出：false
解答
这个问题可以通过深度优先搜索（DFS）来解决。我们需要从根节点开始，沿着每条路径向下遍历，直到到达叶子节点，并检查路径上节点值的和是否等于目标和。
解题思路
- 递归终止条件
- 如果当前节点是
null，说明当前路径不存在，返回false - 如果当前节点是叶子节点（即没有左右子节点），检查当前节点的值是否等于剩余的目标和。如果是，返回
true，否则返回false
- 递归逻辑
- 从根节点开始，沿着左子树和右子树递归遍历
- 每次递归时，将当前节点的值从目标和中减去，并传递给子节点
- 如果左子树或右子树的递归结果为
true，说明存在满足条件的路径，返回true
- 返回结果
- 如果所有路径都不满足条件，返回
false
Code
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if (!root) return false;
if (!root.left && !root.right) return root.val === targetSum;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}