6.二叉树
一棵二叉树找到是否有一条路径（从根节点到子节点），节点值的和为 N
题目
给定一个二叉树和一个目标和 N，判断该二叉树中是否存在一条从根节点到叶子节点（即路径）的路径，使得路径上所有节点的值相加等于目标和 N。
示例
给定二叉树:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
和目标和 N = 22
返回 true，因为存在一条路径 5 -> 4 -> 11 -> 2，使得路径上所有节点的值相加等于目标和 22。
给定二叉树:
1
/ \
2 3
和目标和 N = 6
返回 false，因为不存在这样的路径。
参考答案
DETAILS
// 定义二叉树节点
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
// 检查是否存在路径和等于目标和的函数
function hasPathSum(root, N) {
// 如果根节点为空，返回 false
if (!root) {
return false;
}
// 如果是叶子节点，检查节点值是否等于剩余目标和
if (!root.left && !root.right) {
return root.val === N;
}
// 递归检查左子树和右子树，目标和减去当前节点的值
const remainingSum = N - root.val;
return (
hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum)
);
}
// 示例使用
// 构造示例 1 中的二叉树
const root1 = new TreeNode(5);
root1.left = new TreeNode(4);
root1.right = new TreeNode(8);
root1.left.left = new TreeNode(11);
root1.left.left.left = new TreeNode(7);
root1.left.left.right = new TreeNode(2);
root1.right.left = new TreeNode(13);
root1.right.right = new TreeNode(4);
root1.right.right.right = new TreeNode(1);
// 检查路径和是否等于 22
console.log(hasPathSum(root1, 22)); // 输出: true
// 构造示例 2 中的二叉树
const root2 = new TreeNode(1);
root2.left = new TreeNode(2);
root2.right = new TreeNode(3);
// 检查路径和是否等于 6
console.log(hasPathSum(root2, 6)); // 输出: false