236. 二叉树的最近公共祖先
核心逻辑
本解法采用 递归 的策略：
- 递归终止条件：
- 如果
root == null，说明走到底了还没找到 p 和 q ，返回null。 - 如果
root就是p或q其中一个，则直接返回root。
- 如果
- 递归搜索：
- 分别在
root的左子树 (left) 和右子树 (right) 中搜索p和q。
- 分别在
- 合并结果：
- 若
left不为空且right不为空，说明p和q分别位于root的两侧，因此root就是最近公共祖先，返回root。 - 若只有
left不为空，说明p和q都在左子树中，返回left。 - 若只有
right不为空，说明p和q都在右子树中，返回right。 - 若
left和right都为空，说明该子树不包含p或q，返回null。
- 若
🔥代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 终止条件 1：遍历到空节点
if (root == null) {
return null;
}
// 终止条件 2：当前节点就是目标节点 p 或 q（直接比较引用）
if (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;
} else if (left != null && right == null) {
return left;
} else if (right != null && left == null) {
return right;
} else {
return null;
}
}
}
📚遇到的问题：
这是最初思路。首先，原思路认为
left和right在子树中绝对存在，递归时一定能找到，这一点没毛病。但随后产生了一个错误想法：认为
left和right不会为null。由于叶子节点本身没有左右子节点，所以以叶子节点为基准时，
left和right就是真实的null。而原代码在逻辑处理上直接return root，没有返回null。这样一来，由底向上返回时，各个节点都会返回root，最终直接返回了根节点，导致错误。