979. Distribute Coins in Binary Tree Medium

1/**
2 * [979] Distribute Coins in Binary Tree
3 *
4 * You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
5 * In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
6 * Return the minimum number of moves required to make every node have exactly one coin.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree1.png" style="width: 250px; height: 236px;" />
10 * Input: root = [3,0,0]
11 * Output: 2
12 * Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
13 * 
14 * Example 2:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree2.png" style="width: 250px; height: 236px;" />
16 * Input: root = [0,3,0]
17 * Output: 3
18 * Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
19 * 
20 *  
21 * Constraints:
22 * 
23 * 	The number of nodes in the tree is n.
24 * 	1 <= n <= 100
25 * 	0 <= Node.val <= n
26 * 	The sum of all Node.val is n.
27 * 
28 */
29pub struct Solution {}
30use crate::util::tree::{TreeNode, to_tree};
31
32// problem: https://leetcode.com/problems/distribute-coins-in-binary-tree/
33// discuss: https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37// Definition for a binary tree node.
38// #[derive(Debug, PartialEq, Eq)]
39// pub struct TreeNode {
40//   pub val: i32,
41//   pub left: Option<Rc<RefCell<TreeNode>>>,
42//   pub right: Option<Rc<RefCell<TreeNode>>>,
43// }
44// 
45// impl TreeNode {
46//   #[inline]
47//   pub fn new(val: i32) -> Self {
48//     TreeNode {
49//       val,
50//       left: None,
51//       right: None
52//     }
53//   }
54// }
55use std::rc::Rc;
56use std::cell::RefCell;
57impl Solution {
58    pub fn distribute_coins(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_979() {
71    }
72}
73