面试经典150题 P236 二叉树的最近公共祖先

---

时间轴

时间轴

2025-10-29

init

后序遍历

---

题目：

P236 二叉树的最近公共祖先

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

后序遍历，当要访问某一个节点时，此时栈中的节点就是从 root 到当前节点的路径上的所有节点。找到 root 到 p 和 q 的两条路径，然后求这两条路径最后一个相同的节点。注意这里题目说每个节点值时不同的，因此我们可以直接比较 Rc，这种比较方法比较的时 Rc 指向的值，使用 Rc::ptr_eq 方法可以比较两个 Rc 是否是从同一个 Rc 克隆的

究极无敌恶心的语法：

// 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();
        // 后序遍历非递归
        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!");
}

递归写法：

/**
 * 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：如果 root 是空，或就是 p 或 q，直接返回
        if (!root || root == p || root == q) return root;

        // 在左子树中找 p 或 q
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        // 在右子树中找 p 或 q
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 情况1：左右都找到 → 当前 root 就是最近公共祖先
        if (left && right) return root;

        // 情况2：只找到一个 → 把那个往上返回
        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); // 左子树找p或q
                TreeNode *right = lowestCommonAncestor(root->right, p, q); // 右子树找p或q

                if (left && right) // 如果左右子树都找到
                        return root;

                return left == nullptr ? right : left; // 否则返回找到的那个
        }
};