129. Sum Root to Leaf Numbers Medium

1/**
2 * [129] Sum Root to Leaf Numbers
3 *
4 * You are given the root of a binary tree containing digits from 0 to 9 only.
5 * Each root-to-leaf path in the tree represents a number.
6 * 
7 * 	For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
8 * 
9 * Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
10 * A leaf node is a node with no children.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg" style="width: 212px; height: 182px;" />
14 * Input: root = [1,2,3]
15 * Output: 25
16 * Explanation:
17 * The root-to-leaf path 1->2 represents the number 12.
18 * The root-to-leaf path 1->3 represents the number 13.
19 * Therefore, sum = 12 + 13 = 25.
20 * 
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg" style="width: 292px; height: 302px;" />
23 * Input: root = [4,9,0,5,1]
24 * Output: 1026
25 * Explanation:
26 * The root-to-leaf path 4->9->5 represents the number 495.
27 * The root-to-leaf path 4->9->1 represents the number 491.
28 * The root-to-leaf path 4->0 represents the number 40.
29 * Therefore, sum = 495 + 491 + 40 = 1026.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	The number of nodes in the tree is in the range [1, 1000].
35 * 	0 <= Node.val <= 9
36 * 	The depth of the tree will not exceed 10.
37 * 
38 */
39pub struct Solution {}
40use crate::util::tree::{TreeNode, to_tree};
41
42// problem: https://leetcode.com/problems/sum-root-to-leaf-numbers/
43// discuss: https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47// Definition for a binary tree node.
48// #[derive(Debug, PartialEq, Eq)]
49// pub struct TreeNode {
50//   pub val: i32,
51//   pub left: Option<Rc<RefCell<TreeNode>>>,
52//   pub right: Option<Rc<RefCell<TreeNode>>>,
53// }
54// 
55// impl TreeNode {
56//   #[inline]
57//   pub fn new(val: i32) -> Self {
58//     TreeNode {
59//       val,
60//       left: None,
61//       right: None
62//     }
63//   }
64// }
65use std::rc::Rc;
66use std::cell::RefCell;
67impl Solution {
68    pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_129() {
81    }
82}
83