113. Path Sum II

Description of the Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints: The number of nodes in the tree is in the range [0, 5000].

  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Solution

Tags: Permutation and Combination

Explanation

39. Combination Sum explains the approach we used.

Code(Rust)

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> Vec<Vec<i32>> {
        let mut answer = Vec::new();
        Self::dfs(root, target_sum, &mut Vec::new(), &mut answer);
        answer
    }
    fn dfs(
        node: Option<Rc<RefCell<TreeNode>>>,
        target_sum: i32,
        v: &mut Vec<i32>,
        answer: &mut Vec<Vec<i32>>,
    ) {
        if let Some(n) = node {
            let val = n.borrow().val;
            let l = n.borrow().left.clone();
            let r = n.borrow().right.clone();
            v.push(val);
            if target_sum == val && l.is_none() && r.is_none() {
                answer.push(v.clone());
            }
            Self::dfs(l, target_sum - val, v, answer);
            Self::dfs(r, target_sum - val, v, answer);
            v.pop();
        }
    }
}

Complexity (n is the number of node and h is height of tree)

Time complexity:

  • Worst case: \(\Theta(n)\)
    • Traverse all nodes

Auxiliary Space:

  • \( O(h) \)
    • The size of temp array and call stack are bound by the height of the tree