Question

112. Path Sum

中文文档

Description

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 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

Solutions

Solution 1: Recursion

Starting from the root node, recursively traverse the tree and update the value of the node to the path sum from the root node to that node. When you traverse to a leaf node, determine whether this path sum is equal to the target value. If it is equal, return true, otherwise return false.

The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. Each node is visited once.

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(root, s):
      if root is None:
        return False
      s += root.val
      if root.left is None and root.right is None and s == targetSum:
        return True
      return dfs(root.left, s) or dfs(root.right, s)

    return dfs(root, 0)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public boolean hasPathSum(TreeNode root, int targetSum) {
    return dfs(root, targetSum);
  }

  private boolean dfs(TreeNode root, int s) {
    if (root == null) {
      return false;
    }
    s -= root.val;
    if (root.left == null && root.right == null && s == 0) {
      return true;
    }
    return dfs(root.left, s) || dfs(root.right, s);
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  bool hasPathSum(TreeNode* root, int targetSum) {
    function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int s) -> int {
      if (!root) return false;
      s += root->val;
      if (!root->left && !root->right && s == targetSum) return true;
      return dfs(root->left, s) || dfs(root->right, s);
    };
    return dfs(root, 0);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
  var dfs func(*TreeNode, int) bool
  dfs = func(root *TreeNode, s int) bool {
    if root == nil {
      return false
    }
    s += root.Val
    if root.Left == nil && root.Right == nil && s == targetSum {
      return true
    }
    return dfs(root.Left, s) || dfs(root.Right, s)
  }
  return dfs(root, 0)
}

/**
 * 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, targetSum: number): boolean {
  if (root === null) {
    return false;
  }
  const { val, left, right } = root;
  if (left === null && right === null) {
    return targetSum - val === 0;
  }
  return hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val);
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
    match root {
      None => false,
      Some(node) => {
        let mut node = node.borrow_mut();
        // 确定叶结点身份
        if node.left.is_none() && node.right.is_none() {
          return target_sum - node.val == 0;
        }
        let val = node.val;
        Self::has_path_sum(node.left.take(), target_sum - val) ||
          Self::has_path_sum(node.right.take(), target_sum - val)
      }
    }
  }
}

/**
 * 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) {
  function dfs(root, s) {
    if (!root) return false;
    s += root.val;
    if (!root.left && !root.right && s == targetSum) return true;
    return dfs(root.left, s) || dfs(root.right, s);
  }
  return dfs(root, 0);
};