1123. Lowest Common Ancestor of Deepest Leaves Medium

1/**
2 * [1123] Lowest Common Ancestor of Deepest Leaves
3 *
4 * Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.
5 * Recall that:
6 * 
7 * 	The node of a binary tree is a leaf if and only if it has no children
8 * 	The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
9 * 	The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.
10 * 
11 *  
12 * Example 1:
13 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png" style="width: 600px; height: 510px;" />
14 * Input: root = [3,5,1,6,2,0,8,null,null,7,4]
15 * Output: [2,7,4]
16 * Explanation: We return the node with value 2, colored in yellow in the diagram.
17 * The nodes coloured in blue are the deepest leaf-nodes of the tree.
18 * Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.
19 * Example 2:
20 * 
21 * Input: root = [1]
22 * Output: [1]
23 * Explanation: The root is the deepest node in the tree, and it's the lca of itself.
24 * 
25 * Example 3:
26 * 
27 * Input: root = [0,1,3,null,2]
28 * Output: [2]
29 * Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	The number of nodes in the tree will be in the range [1, 1000].
35 * 	0 <= Node.val <= 1000
36 * 	The values of the nodes in the tree are unique.
37 * 
38 *  
39 * Note: This question is the same as 865: <a href="https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/" target="_blank">https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/</a>
40 * 
41 */
42pub struct Solution {}
43use crate::util::tree::{TreeNode, to_tree};
44
45// problem: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
46// discuss: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/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 lca_deepest_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
72        Some(Rc::new(RefCell::new(TreeNode::new(0))))
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_1123() {
84    }
85}
86