236. Lowest Common Ancestor of a Binary Tree Medium

1/**
2 * [236] Lowest Common Ancestor of a Binary Tree
3 *
4 * Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
5 * According to the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor" target="_blank">definition of LCA on Wikipedia</a>: &ldquo;The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).&rdquo;
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" />
9 * Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
10 * Output: 3
11 * Explanation: The LCA of nodes 5 and 1 is 3.
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" />
15 * Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
16 * Output: 5
17 * Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
18 * 
19 * Example 3:
20 * 
21 * Input: root = [1,2], p = 1, q = 2
22 * Output: 1
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	The number of nodes in the tree is in the range [2, 10^5].
28 * 	-10^9 <= Node.val <= 10^9
29 * 	All Node.val are unique.
30 * 	p != q
31 * 	p and q will exist in the tree.
32 * 
33 */
34pub struct Solution {}
35use crate::util::tree::{TreeNode, to_tree};
36
37// problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
38// discuss: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for a binary tree node.
43// #[derive(Debug, PartialEq, Eq)]
44// pub struct TreeNode {
45//   pub val: i32,
46//   pub left: Option<Rc<RefCell<TreeNode>>>,
47//   pub right: Option<Rc<RefCell<TreeNode>>>,
48// }
49// 
50// impl TreeNode {
51//   #[inline]
52//   pub fn new(val: i32) -> Self {
53//     TreeNode {
54//       val,
55//       left: None,
56//       right: None
57//     }
58//   }
59// }
60use std::rc::Rc;
61use std::cell::RefCell;
62impl Solution {
63    pub fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
64        Some(Rc::new(RefCell::new(TreeNode::new(0))))
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_236() {
76    }
77}
78