知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 二叉树的最近公共祖先(LCA)— 大白话讲解 ## 题目是什么 给你一棵二叉树,再给你树中的两个节点 p 和 q,让你找到它们的"最近公共祖先"。 最近公共祖先的意思:从根节点往下看,p 和 q 共同的祖先可能有很多个(根节点肯定是),但我们要找离它们最近的那个。 ``` 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 p = 5, q = 1 → 最近公共祖先 = 3 p = 5, q = 4 → 最近公共祖先 = 5(自己也算自己的祖先) ``` ## 核心思路:大白话版 想象你是一个侦探,站在树的根节点,派两个小弟分别去左子树和右子树找 p 和 q。 小弟回来汇报有三种情况: 1. 左边找到了,右边也找到了 → 说明 p 和 q 分居两侧,当前节点就是答案 2. 左边找到了,右边没找到 → 说明 p 和 q 都在左边,答案在左边 3. 左边没找到,右边找到了 → 说明 p 和 q 都在右边,答案在右边 就这么简单。递归地往下问,每个节点都做同样的判断。 ## 用生活例子理解 把二叉树想象成一个家族族谱: ``` 爷爷 / \ 爸爸 叔叔 / \ \ 你 姐姐 堂弟 ``` - "你"和"姐姐"的最近公共祖先 → 爸爸 - "你"和"堂弟"的最近公共祖先 → 爷爷 - "爸爸"和"你"的最近公共祖先 → 爸爸(爸爸是你的祖先,也是自己的祖先) 规律就是:沿着族谱往上找,两个人第一次"汇合"的那个人,就是最近公共祖先。 ## 代码实现(Java) ```java class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 递归终止条件 if (root == null || root == p || root == q) { return root; } // 去左子树找 TreeNode left = lowestCommonAncestor(root.left, p, q); // 去右子树找 TreeNode right = lowestCommonAncestor(root.right, p, q); // 判断结果 if (left != null && right != null) { // 左右都找到了 → 当前节点就是答案 return root; } // 哪边找到了就返回哪边 return left != null ? left : right; } ``` ## 逐行拆解,彻底搞懂 ### 第一行:递归终止条件 ```java if (root == null || root == p || root == q) { return root; } ``` 三种情况直接返回: - `root == null`:走到空节点了,说明这条路没找到,返回 null - `root == p`:找到 p 了,返回 p - `root == q`:找到 q 了,返回 q 为什么找到 p 就直接返回,不继续往下找 q 了? 因为如果 q 是 p 的子孙,那 p 本身就是答案(祖先包含自己)。 如果 q 不在 p 的子树里,那 q 会在另一侧被找到。 ### 第二行:递归搜索 ```java TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); ``` 派两个小弟分别去左子树和右子树找。返回值的含义: - 返回 null → 那边没找到 p 也没找到 q - 返回非 null → 那边找到了 p 或 q(或者找到了它们的 LCA) ### 第三行:汇总结果 ```java if (left != null && right != null) return root; return left != null ? left : right; ``` ``` 情况 1:left != null && right != null 左边找到一个,右边找到一个 说明 p 和 q 分别在当前节点的两侧 → 当前节点就是最近公共祖先 情况 2:left != null && right == null 只有左边找到了 说明 p 和 q 都在左子树里(或者左边直接找到了 LCA) → 返回左边的结果 情况 3:left == null && right != null 只有右边找到了 → 返回右边的结果 情况 4:left == null && right == null 两边都没找到(理论上不会发生,因为题目保证 p 和 q 存在) → 返回 null ``` ## 画图模拟一遍 ``` 找 p=5, q=4 的 LCA: 3 ← 第 1 步:从 3 开始 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 递归过程(从下往上看): 节点 6:不是 p 也不是 q,左右都是 null → 返回 null 节点 7:不是 p 也不是 q,左右都是 null → 返回 null 节点 4:root == q → 返回 4 ✓ 节点 2:左边返回 null(7),右边返回 4 → 只有右边有结果 → 返回 4 节点 5:root == p → 直接返回 5 ✓ (不会再往下递归了) 回到节点 3: 左边返回 5(找到了 p) 右边:节点 1 那边找不到 p 和 q → 返回 null → 只有左边有结果 → 返回 5 最终答案:5 为什么是 5?因为 5 是 p 本身,而 q=4 是 5 的子孙 所以 5 就是它们的最近公共祖先 ``` 再看 p=5, q=1: ``` 节点 5:root == p → 返回 5 节点 1:root == q → 返回 1 回到节点 3: 左边返回 5 ✓ 右边返回 1 ✓ 两边都不为 null → 返回当前节点 3 最终答案:3 ``` ## 复杂度分析 ``` 时间复杂度:O(n) 每个节点最多访问一次 空间复杂度:O(n) 递归调用栈的深度,最坏情况(链状树)为 n 平均情况(平衡树)为 O(log n) ``` ## Python 版本 ```python def lowestCommonAncestor(root, p, q): if not root or root == p or root == q: return root left = lowestCommonAncestor(root.left, p, q) right = lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right ``` ## 变体:二叉搜索树的 LCA 如果是二叉搜索树(BST),可以利用有序性优化: ```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val < root.val && q.val < root.val) { root = root.left; // p 和 q 都在左边 } else if (p.val > root.val && q.val > root.val) { root = root.right; // p 和 q 都在右边 } else { return root; // 分叉了,当前节点就是答案 } } return null; } // 时间 O(h),空间 O(1),h 是树的高度 ``` BST 版本更直观:从根节点往下走,p 和 q 的值一个大一个小(或等于当前节点)的时候,就是分叉点,也就是 LCA。 ## 一句话总结 后序遍历,从下往上汇报:左右都找到了就是当前节点,只有一边找到了就往上传递。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入