112. Path Sum

[Tcdian]

112. Path Sum

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

Note

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

Example

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

[Tcdian]

Solution

• JavaScript Solution

/**
 * 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} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    let accumVal = 0;
    let result = false;
    dfs(root);
    return result;

    function dfs(root) {
        if (root === null || result) {
            return;
        }
        accumVal += root.val;
        if (accumVal === sum && root.left === null && root.right === null) {
            result = true;
            return;
        }
        dfs(root.left);
        dfs(root.right);
        accumVal -= root.val;
    }
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * 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)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, sum: number): boolean {
    let accumVal = 0;
    let result = false;
    dfs(root);
    return result;

    function dfs(root: TreeNode | null) {
        if (root === null || result) {
            return;
        }
        accumVal += root.val;
        if (accumVal === sum && root.left === null && root.right === null) {
            result = true;
            return;
        }
        dfs(root.left);
        dfs(root.right);
        accumVal -= root.val;
    }
};