[LeetCode] 112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 –> 2): The sum is 3.
(1 –> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

路径总和。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - DFS/recursive

复杂度

时间O(n)
空间O(h)

代码

Java实现

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

JavaScript实现

/**
 * 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) {
    if (root === null) {
        return false;
    }
    if (root.left === null && root.right === null) {
        return sum === root.val;
    }
    return (
        hasPathSum(root.left, sum - root.val) ||
        hasPathSum(root.right, sum - root.val)
    );
};

思路二 - BFS/iterative

用一个 stack 存储遍历到的节点。当加入某个节点的时候，如果这个节点没有孩子节点，需要判断加入这个节点之后的值是否等于 sum；如果这个节点有孩子节点，接着遍历它的孩子节点，将cur.val + cur.left.val （cur.val + cur.right.val）加入 stack。

复杂度

时间O(n)
空间O(n) - n is the number of nodes

代码

Java实现

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // corner case
        if (root == null) {
            return false;
        }

        // normal case
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.left == null && cur.right == null) {
                if (cur.val == sum) {
                    return true;
                }
            }
            if (cur.right != null) {
                stack.push(cur.right);
                cur.right.val += cur.val;
            }
            if (cur.left != null) {
                stack.push(cur.left);
                cur.left.val += cur.val;
            }
        }
        return false;
    }
}

JavaScript实现

/**
 * 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) {
    if (!root) {
        return false;
    }
    let stack = [root];
    while (stack.length) {
        let cur = stack.pop();
        if (!cur.left && !cur.right && cur.val === sum) {
            return true;
        }
        if (cur.right) {
            cur.right.val += cur.val;
            stack.push(cur.right);
        }
        if (cur.left) {
            cur.left.val += cur.val;
            stack.push(cur.left);
        }
    }
    return false;
};

相关题目

112. Path Sum
113. Path Sum II
437. Path Sum III
1457. Pseudo-Palindromic Paths in a Binary Tree