814. Binary Tree Pruning Medium

1/**
2 * [814] Binary Tree Pruning
3 *
4 * Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
5 * A subtree of a node node is node plus every node that is a descendant of node.
6 *  
7 * Example 1:
8 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png" style="width: 500px; height: 140px;" />
9 * Input: root = [1,null,0,0,1]
10 * Output: [1,null,0,null,1]
11 * Explanation: 
12 * Only the red nodes satisfy the property "every subtree not containing a 1".
13 * The diagram on the right represents the answer.
14 * 
15 * Example 2:
16 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png" style="width: 500px; height: 115px;" />
17 * Input: root = [1,0,1,0,0,0,1]
18 * Output: [1,null,1,null,1]
19 * 
20 * Example 3:
21 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png" style="width: 500px; height: 134px;" />
22 * Input: root = [1,1,0,1,1,0,1,0]
23 * Output: [1,1,0,1,1,null,1]
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	The number of nodes in the tree is in the range [1, 200].
29 * 	Node.val is either 0 or 1.
30 * 
31 */
32pub struct Solution {}
33use crate::util::tree::{TreeNode, to_tree};
34
35// problem: https://leetcode.com/problems/binary-tree-pruning/
36// discuss: https://leetcode.com/problems/binary-tree-pruning/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40// Definition for a binary tree node.
41// #[derive(Debug, PartialEq, Eq)]
42// pub struct TreeNode {
43//   pub val: i32,
44//   pub left: Option<Rc<RefCell<TreeNode>>>,
45//   pub right: Option<Rc<RefCell<TreeNode>>>,
46// }
47// 
48// impl TreeNode {
49//   #[inline]
50//   pub fn new(val: i32) -> Self {
51//     TreeNode {
52//       val,
53//       left: None,
54//       right: None
55//     }
56//   }
57// }
58use std::rc::Rc;
59use std::cell::RefCell;
60impl Solution {
61    pub fn prune_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
62        Some(Rc::new(RefCell::new(TreeNode::new(0))))
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_814() {
74    }
75}
76