865. Smallest Subtree with all the Deepest Nodes Medium

1/**
2 * [865] Smallest Subtree with all the Deepest Nodes
3 *
4 * Given the root of a binary tree, the depth of each node is the shortest distance to the root.
5 * Return the smallest subtree such that it contains all the deepest nodes in the original tree.
6 * A node is called the deepest if it has the largest depth possible among any node in the entire tree.
7 * The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.
8 *  
9 * Example 1:
10 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png" style="width: 600px; height: 510px;" />
11 * Input: root = [3,5,1,6,2,0,8,null,null,7,4]
12 * Output: [2,7,4]
13 * Explanation: We return the node with value 2, colored in yellow in the diagram.
14 * The nodes coloured in blue are the deepest nodes of the tree.
15 * Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
16 * 
17 * Example 2:
18 * 
19 * Input: root = [1]
20 * Output: [1]
21 * Explanation: The root is the deepest node in the tree.
22 * 
23 * Example 3:
24 * 
25 * Input: root = [0,1,3,null,2]
26 * Output: [2]
27 * Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	The number of nodes in the tree will be in the range [1, 500].
33 * 	0 <= Node.val <= 500
34 * 	The values of the nodes in the tree are unique.
35 * 
36 *  
37 * Note: This question is the same as 1123: <a href="https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/" target="_blank">https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/</a>
38 * 
39 */
40pub struct Solution {}
41use crate::util::tree::{TreeNode, to_tree};
42
43// problem: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
44// discuss: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48// Definition for a binary tree node.
49// #[derive(Debug, PartialEq, Eq)]
50// pub struct TreeNode {
51//   pub val: i32,
52//   pub left: Option<Rc<RefCell<TreeNode>>>,
53//   pub right: Option<Rc<RefCell<TreeNode>>>,
54// }
55// 
56// impl TreeNode {
57//   #[inline]
58//   pub fn new(val: i32) -> Self {
59//     TreeNode {
60//       val,
61//       left: None,
62//       right: None
63//     }
64//   }
65// }
66use std::rc::Rc;
67use std::cell::RefCell;
68impl Solution {
69    pub fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
70        Some(Rc::new(RefCell::new(TreeNode::new(0))))
71    }
72}
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_865() {
82    }
83}
84