113. Path Sum II Medium

1/**
2 * [113] Path Sum II
3 *
4 * 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.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg" style="width: 500px; height: 356px;" />
9 * Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
10 * Output: [[5,4,11,2],[5,8,4,5]]
11 * Explanation: There are two paths whose sum equals targetSum:
12 * 5 + 4 + 11 + 2 = 22
13 * 5 + 8 + 4 + 5 = 22
14 *
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg" style="width: 212px; height: 181px;" />
17 * Input: root = [1,2,3], targetSum = 5
18 * Output: []
19 *
20 * Example 3:
21 *
22 * Input: root = [1,2], targetSum = 0
23 * Output: []
24 *
25 *  
26 * Constraints:
27 *
28 * The number of nodes in the tree is in the range [0, 5000].
29 * -1000 <= Node.val <= 1000
30 * -1000 <= targetSum <= 1000
31 *
32 */
33pub struct Solution {}
34#[allow(unused_imports)]
35use crate::util::tree::{to_tree, TreeNode};
36
37// problem: https://leetcode.com/problems/path-sum-ii/
38// discuss: https://leetcode.com/problems/path-sum-ii/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for a binary tree node.
43// #[derive(Debug, PartialEq, Eq)]
44// pub struct TreeNode {
45//   pub val: i32,
46//   pub left: Option<Rc<RefCell<TreeNode>>>,
47//   pub right: Option<Rc<RefCell<TreeNode>>>,
48// }
49//
50// impl TreeNode {
51//   #[inline]
52//   pub fn new(val: i32) -> Self {
53//     TreeNode {
54//       val,
55//       left: None,
56//       right: None
57//     }
58//   }
59// }
60use std::cell::RefCell;
61use std::rc::Rc;
62impl Solution {
63    pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> Vec<Vec<i32>> {
64        let mut result = vec![];
65        let mut current = vec![];
66        Self::find_path_sum(root.as_ref(), target_sum, &mut result, &mut current);
67        result
68    }
69
70    fn find_path_sum(
71        root: Option<&Rc<RefCell<TreeNode>>>,
72        target_sum: i32,
73        result: &mut Vec<Vec<i32>>,
74        current: &mut Vec<i32>,
75    ) {
76        match root {
77            Some(r) => {
78                let b = r.borrow();
79                let remains = target_sum - b.val;
80                let right = b.right.as_ref();
81                let left = b.left.as_ref();
82                current.push(b.val);
83                if right.is_none() && left.is_none() && remains == 0 {
84                    result.push(current.clone());
85                }
86                Self::find_path_sum(right, remains, result, current);
87                Self::find_path_sum(left, remains, result, current);
88                current.pop();
89            }
90            None => {}
91        }
92    }
93}
94
95// submission codes end
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100    use crate::tree;
101
102    #[test]
103    fn test_113() {
104        assert_eq!(
105            Solution::path_sum(tree![5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], 22),
106            vec![vec![5, 8, 4, 5], vec![5, 4, 11, 2]]
107        );
108        let empty: Vec<Vec<i32>> = Vec::new();
109        assert_eq!(Solution::path_sum(tree![1, 2, 3], 5), empty);
110    }
111}
112