236. 二叉树的最近公共祖先
题目描述
输入一棵普通二叉树的根节点 root，以及树中两个不同的节点 p 和 q。树用层序数组表示，空位记为 null；p、q 用节点值给出。
若节点 x 同时是 p 和 q 的祖先，它就是二者的公共祖先。节点本身也算自己的祖先。所有公共祖先里深度最大的一个，叫做最近公共祖先。
返回 p 和 q 的最近公共祖先。
示例 1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3
解释：5 和 1 分别是根的左右孩子，最近公共祖先是根节点 3。
示例 2
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5
解释：4 在节点 5 的子树里，5 自身也算祖先，所以答案是 5。
示例 3
输入：root = [1,2], p = 1, q = 2 输出：1
解释：2 是 1 的孩子，最近公共祖先是 1。
数据范围
- 节点个数在
[2, 10^5]之间。 -10^9 <= Node.val <= 10^9- 所有
Node.val两两不同。 p != qp和q都在这棵树中。
解题思路：后序递归
后序递归：遇到 p 或 q 直接返回；左右都返回非空说明当前节点是分叉点，否则向上传递唯一非空结果。
为什么正确
递归返回子树中找到的目标节点，或已经确定的最近公共祖先。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
比较节点身份而非值；当某个目标本身是另一个目标的祖先时，应直接返回该目标。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lowestCommonAncestor(self, root, p, q):
if root is None or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or rightclass Solution {
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;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
return left ? left : right;
}
};func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
return right
}var lowestCommonAncestor = function(root, p, q) {
if (root === null || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) {
return root;
}
return left || right;
};function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (root === null || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) {
return root;
}
return left || right;
};其他解法
后序递归代码短，空间只有递归栈 O(h)；记录父节点的做法用 O(n) 空间把问题变成链表交点，并且可以完全迭代。
解法 2：记录父节点 时间 O(n)，空间 O(n)
用显式栈遍历整棵树，把每个节点的父节点记入哈希表。从 p 沿父指针一直走到根，把经过的节点放入集合。再从 q 沿父指针向上走，第一个在集合中的节点就是答案。
不用递归，深链树不会栈溢出。需要哈希表和集合，空间 O(n)。把问题转成“两条向上的链表求交点”，便于理解。
class Solution:
def lowestCommonAncestor(self, root, p, q):
parent = {root: None}
stack = [root]
while stack:
node = stack.pop()
for child in (node.left, node.right):
if child:
parent[child] = node
stack.append(child)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return qclass Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
for (TreeNode child : new TreeNode[]{node.left, node.right}) {
if (child != null) {
parent.put(child, node);
stack.push(child);
}
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.contains(q)) q = parent.get(q);
return q;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*, TreeNode*> parent;
parent[root] = nullptr;
vector<TreeNode*> stk{root};
while (!stk.empty()) {
TreeNode* node = stk.back();
stk.pop_back();
for (TreeNode* child : {node->left, node->right}) {
if (child) {
parent[child] = node;
stk.push_back(child);
}
}
}
unordered_set<TreeNode*> ancestors;
while (p) {
ancestors.insert(p);
p = parent[p];
}
while (!ancestors.count(q)) q = parent[q];
return q;
}
};func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
parent := map[*TreeNode]*TreeNode{root: nil}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, child := range []*TreeNode{node.Left, node.Right} {
if child != nil {
parent[child] = node
stack = append(stack, child)
}
}
}
ancestors := map[*TreeNode]bool{}
for p != nil {
ancestors[p] = true
p = parent[p]
}
for !ancestors[q] {
q = parent[q]
}
return q
}var lowestCommonAncestor = function(root, p, q) {
const parent = new Map([[root, null]]);
const stack = [root];
while (stack.length) {
const node = stack.pop();
for (const child of [node.left, node.right]) {
if (child) {
parent.set(child, node);
stack.push(child);
}
}
}
const ancestors = new Set();
while (p) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.has(q)) q = parent.get(q);
return q;
};function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
const parent = new Map<TreeNode, TreeNode | null>([[root!, null]]);
const stack: TreeNode[] = [root!];
while (stack.length) {
const node = stack.pop()!;
for (const child of [node.left, node.right]) {
if (child) {
parent.set(child, node);
stack.push(child);
}
}
}
const ancestors = new Set<TreeNode>();
while (p) {
ancestors.add(p);
p = parent.get(p)!;
}
while (!ancestors.has(q!)) q = parent.get(q!)!;
return q;
}