深色模式
BM29 二叉树中和为某一值的路径
方法一：前序遍历
- 这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。
- 具体思路如下图所示：
ts
/*class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
export function hasPathSum(root: TreeNode, sum: number): boolean {
// write code here
if (!root) return false;
if(!root.left && !root.right && root.val === sum) return true;
return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum - root.val)
}方法二：层次遍历
- 同样我们也可以通过层次遍历，同步推进每一条路径在每一层的值，从而判断二叉树中是否存在节点和为指定值的路径。只需要去判断叶子节点的和是否为要求的值即可。
- 具体思路如下图所示：
ts
/*class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
type NodePair = {
node : TreeNode,
sum: number
}
export function hasPathSum(root: TreeNode, sum: number): boolean {
// write code here
if (!root) return false;
var nodepairs: NodePair[] = [];
nodepairs.push({node: root, sum: root.val})
while(nodepairs.length) {
const nodepair: NodePair = nodepairs.pop();
if(nodepair.node.left) {
nodepairs.push({node: nodepair.node.left, sum: nodepair.sum + nodepair.node.left.val} )
}
if(nodepair.node.right) {
nodepairs.push({node: nodepair.node.right, sum: nodepair.sum + nodepair.node.right.val} )
}
if(!nodepair.node.left && !nodepair.node.right ) {
if(nodepair.sum === sum) return true;
}
}
return false;
}