112. Path Sum Easy

1/**
2 * [112] Path Sum
3 *
4 * 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.
5 * A leaf is a node with no children.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsum1.jpg" style="width: 500px; height: 356px;" />
9 * Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
10 * Output: true
11 * Explanation: The root-to-leaf path with the target sum is shown.
12 *
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg" />
15 * Input: root = [1,2,3], targetSum = 5
16 * Output: false
17 * Explanation: There two root-to-leaf paths in the tree:
18 * (1 --> 2): The sum is 3.
19 * (1 --> 3): The sum is 4.
20 * There is no root-to-leaf path with sum = 5.
21 *
22 * Example 3:
23 *
24 * Input: root = [], targetSum = 0
25 * Output: false
26 * Explanation: Since the tree is empty, there are no root-to-leaf paths.
27 *
28 *  
29 * Constraints:
30 *
31 * The number of nodes in the tree is in the range [0, 5000].
32 * -1000 <= Node.val <= 1000
33 * -1000 <= targetSum <= 1000
34 *
35 */
36pub struct Solution {}
37#[allow(unused_imports)]
38use crate::util::tree::{to_tree, TreeNode};
39
40// problem: https://leetcode.com/problems/path-sum/
41// discuss: https://leetcode.com/problems/path-sum/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45// Definition for a binary tree node.
46// #[derive(Debug, PartialEq, Eq)]
47// pub struct TreeNode {
48//   pub val: i32,
49//   pub left: Option<Rc<RefCell<TreeNode>>>,
50//   pub right: Option<Rc<RefCell<TreeNode>>>,
51// }
52//
53// impl TreeNode {
54//   #[inline]
55//   pub fn new(val: i32) -> Self {
56//     TreeNode {
57//       val,
58//       left: None,
59//       right: None
60//     }
61//   }
62// }
63use std::cell::RefCell;
64use std::rc::Rc;
65impl Solution {
66    pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
67        if root.is_none() {
68            return false;
69        }
70        Self::has_path_sum_ref(root.as_ref(), target_sum)
71    }
72
73    fn has_path_sum_ref(root: Option<&Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
74        match root {
75            None => target_sum == 0,
76            Some(r) => {
77                let b = r.borrow();
78                let remains = target_sum - b.val;
79                let right = b.right.as_ref();
80                let left = b.left.as_ref();
81
82                if left.is_none() {
83                    Self::has_path_sum_ref(right, remains)
84                } else if right.is_none() {
85                    Self::has_path_sum_ref(left, remains)
86                } else {
87                    Self::has_path_sum_ref(right, remains) || 
88                    Self::has_path_sum_ref(left, remains)
89                }
90            }
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_112() {
104        assert_eq!(Solution::has_path_sum(tree![1, 2, 3], 5), false);
105        assert_eq!(
106            Solution::has_path_sum(
107                tree![5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1],
108                22
109            ),
110            true
111        );
112        assert_eq!(Solution::has_path_sum(tree![], 0), false);
113    }
114}
115