563. Binary Tree Tilt Easy

1/**
2 * [563] Binary Tree Tilt
3 *
4 * Given the root of a binary tree, return the sum of every tree node's tilt.
5 * The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/20/tilt1.jpg" style="width: 712px; height: 182px;" />
9 * Input: root = [1,2,3]
10 * Output: 1
11 * Explanation: 
12 * Tilt of node 2 : |0-0| = 0 (no children)
13 * Tilt of node 3 : |0-0| = 0 (no children)
14 * Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
15 * Sum of every tilt : 0 + 0 + 1 = 1
16 * 
17 * Example 2:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/20/tilt2.jpg" style="width: 800px; height: 203px;" />
19 * Input: root = [4,2,9,3,5,null,7]
20 * Output: 15
21 * Explanation: 
22 * Tilt of node 3 : |0-0| = 0 (no children)
23 * Tilt of node 5 : |0-0| = 0 (no children)
24 * Tilt of node 7 : |0-0| = 0 (no children)
25 * Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
26 * Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
27 * Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
28 * Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15
29 * 
30 * Example 3:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/20/tilt3.jpg" style="width: 800px; height: 293px;" />
32 * Input: root = [21,7,14,1,1,2,2,3,3]
33 * Output: 9
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	The number of nodes in the tree is in the range [0, 10^4].
39 * 	-1000 <= Node.val <= 1000
40 * 
41 */
42pub struct Solution {}
43use crate::util::tree::{TreeNode, to_tree};
44
45// problem: https://leetcode.com/problems/binary-tree-tilt/
46// discuss: https://leetcode.com/problems/binary-tree-tilt/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50// Definition for a binary tree node.
51// #[derive(Debug, PartialEq, Eq)]
52// pub struct TreeNode {
53//   pub val: i32,
54//   pub left: Option<Rc<RefCell<TreeNode>>>,
55//   pub right: Option<Rc<RefCell<TreeNode>>>,
56// }
57// 
58// impl TreeNode {
59//   #[inline]
60//   pub fn new(val: i32) -> Self {
61//     TreeNode {
62//       val,
63//       left: None,
64//       right: None
65//     }
66//   }
67// }
68use std::rc::Rc;
69use std::cell::RefCell;
70impl Solution {
71    pub fn find_tilt(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
72        0
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_563() {
84    }
85}
86