Interview Classic 150 Questions P236 Lowest Common Ancestor of a Binary Tree

---

Timeline

Timeline

2025-10-29

init

Postorder Traversal

---

Problem:

P236 Lowest Common Ancestor of a Binary Tree

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

Postorder traversal: when about to visit a node, the nodes in the stack are all nodes on the path from root to the current node.
Find the two paths from root to p and q, then find the last common node of these two paths.
Note that the problem states that each node value is different, so we can directly compare Rc. This comparison method compares the values pointed to by Rc. Using the Rc::ptr_eq method can compare whether two Rc are cloned from the same Rc.

Extremely disgusting syntax:

// Definition for a binary tree node.
struct Solution;

#[derive(Debug, PartialEq, Eq)]
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::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

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 p.is_none() || q.is_none() || root.is_none() {
            return None;
        }
        let p = p.unwrap();
        let q = q.unwrap();
        // Non-recursive postorder traversal
        let mut stack = VecDeque::new();
        let mut curr = root;
        let mut last = None;
        let mut p_vec = Vec::default();
        let mut q_vec = Vec::default();

        while curr.is_some() || !stack.is_empty() {
            if p_vec.len() > 0 && q_vec.len() > 0 {
                break;
            }
            if let Some(node) = curr {
                stack.push_back(node.clone());
                curr = node.borrow().left.clone();
            } else {
                let top = stack.back().unwrap().clone();
                let top_borrow = top.borrow();

                if top_borrow.right.is_some() && top_borrow.right != last {
                    curr = top_borrow.right.clone();
                } else {
                    // visit top
                    if top_borrow.val == p.borrow().val {
                        // VecDeque contains the path root->curr node
                        p_vec = stack.iter().cloned().collect();
                    } else if top_borrow.val == q.borrow().val {
                        q_vec = stack.iter().cloned().collect();
                    }
                    stack.pop_back();
                    last = Some(top.clone());
                    curr = None;
                }
            }
        }
        let mut index = 0_usize;
        let mut res = None;
        while index < p_vec.len() && index < q_vec.len() {
            if p_vec[index].borrow().val == q_vec[index].borrow().val {
                res = Some(p_vec[index].clone());
            }
            index += 1;
        }
        res
    }
}

fn main() {
    println!("Hello, world!");
}

Recursive approach:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: if root is null, or is p or q, return directly
        if (!root || root == p || root == q) return root;

        // Find p or q in the left subtree
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        // Find p or q in the right subtree
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // Case 1: Both found → current root is the lowest common ancestor
        if (left && right) return root;

        // Case 2: Only one found → return that one upward
        return left ? left : right;
    }

};

leetcode hot 100 rewrite

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
};

class Solution {
    public:
        TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
        {
                if (root == nullptr || p == root || q == root)
                        return root;

                TreeNode *left = lowestCommonAncestor(root->left, p, q); // Find p or q in left subtree
                TreeNode *right = lowestCommonAncestor(root->right, p, q); // Find p or q in right subtree

                if (left && right) // If both left and right subtrees find
                        return root;

                return left == nullptr ? right : left; // Otherwise return the one found
        }
};