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

In postorder traversal, when about to visit a node, the nodes in the stack at that time are all the 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 says each node’s 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’s are cloned from the same Rc.

Extremely nasty 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 version:

/**
 * 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;

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

        // Case 1: both left and right 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); // Search left subtree for p or q
                TreeNode *right = lowestCommonAncestor(root->right, p, q); // Search right subtree for p or q

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

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