LeetCode-in-All

236. Lowest Common Ancestor of a Binary Tree

Medium

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “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).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2

Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Solution

// Definition for a binary tree node.
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::{HashMap, HashSet};
impl Solution {
    pub fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let (Some(rn), Some(pn), Some(qn)) = (&root, &p, &q) {
            
            if rn.borrow().val == pn.borrow().val || rn.borrow().val == qn.borrow().val {
                return root;
            }

            let left = Self::lowest_common_ancestor(
                rn.borrow().left.as_ref().map(Rc::clone),
                Some(Rc::clone(pn)),
                Some(Rc::clone(qn)),
            );

            let right = Self::lowest_common_ancestor(
                rn.borrow().right.as_ref().map(Rc::clone),
                Some(Rc::clone(pn)),
                Some(Rc::clone(qn)),
            );

            if left.is_some() && right.is_some() {
                return root;
            }

            if left.is_some() {
                return left;
            }

            return right;
        }
        None    
    }
}

This site is open source. Improve this page.