二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树T 的两个结点p、q，最近公共祖先表示为一个结点x，满足x 是p、q 的祖先且x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例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
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
二叉树后序遍历法
给定一棵二叉树和两个节点。两个节点的最近公共祖先只有三种可能：
- 在左子树中
- 在右子树中
- 是根节点
后序遍历二叉树，自下而上检测每个节点是否为公共祖先。因为是自下而上，所以第一个遇到的公共祖先就是最近公共祖先。
举个例子，给定如下二叉树，求节点5和1的最近公共祖先。
首先，自上而下探索到叶子节点。再自下而上检测是否为公共祖先。最底层的7和4都不是公共祖先。
向上检测，6, 2, 0, 8都不是公共祖先。
再向上检测，5, 1都不是公共祖先。
最后，检测根节点，其是公共祖先。且是第一个发现的公共祖先，所以即是最近的公共祖先。
代码
package io.github.rscai.leetcode.bytedance.linktree;
public class Solution1026A {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
TreeNode ancestorNodeOnLeft = lowestCommonAncestor(root.left, p, q);
if (ancestorNodeOnLeft != null) {
return ancestorNodeOnLeft;
}
TreeNode ancestorNodeOnRight = lowestCommonAncestor(root.right, p, q);
if (ancestorNodeOnRight != null) {
return ancestorNodeOnRight;
}
if (isAncestorOf(root, p) && isAncestorOf(root, q)) {
return root;
}
return null;
}
private boolean isAncestorOf(TreeNode node, TreeNode another) {
if (node == null) {
return false;
}
if (node.val == another.val) {
return true;
}
if (isAncestorOf(node.left, another) || isAncestorOf(node.right, another)) {
return true;
}
return false;
}
}
首先，从左子树中寻找最近公共祖先。
然后，从右子树中寻找最近公共祖先。
最后，检测根节点是否为公共祖先。
其中，祖先检测isAncestorOf也是以递归实现的。先检测其是否为自身。
再检测左右子节点是否为其祖先。
复杂度分析
时间复杂度
本演算法先自上而下遍历二叉树，再自下而上检测每个节点。最坏情况下，要检测所有节点。每次检测是否为祖先都要再次遍历以其为根节点的子树。假设整棵二叉树的节点数为，则左右子树的节点数和为。
空间复杂度
空间复杂度为。
重用计算结果
在上一个演算法中，重复遍历子树以检测某节点是否为其它节点的祖先节点。重用这树子树检测结果可以大幅减少计算量。
当自下而上检测节点时，有四种可能：
- 其仅是p的祖先
- 其仅是q的祖先
- 其是p和q的公共
- 其即不是p的祖先，也不是q的祖先
我们分别用p, q, 节点自身和null表示上述四种状态。然后，用这四种状态去替换整根子树。
举个例子，给定如下二叉树和节点5, 8：
自下而上检测。7和4即不是5的祖先，也不是8的祖先。所以替换为null（直接消掉）。
然后，检测6, 2, 0, 8。8是8的祖先。
再然后，检测5, 1。5是5的祖先，保留为原值；1是8的祖先，将整棵子树替换为8。
最后，检测3。其是5, 8的公共祖先，将整棵子树替换为公共祖先3。
代码
package io.github.rscai.leetcode.bytedance.linktree;
public class Solution1026B {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root.val == p.val) {
return p;
}
if (root.val == q.val) {
return q;
}
TreeNode ancestorNodeOnLeft = lowestCommonAncestor(root.left, p, q);
if (ancestorNodeOnLeft != null && ancestorNodeOnLeft.val != p.val
&& ancestorNodeOnLeft.val != q.val) {
return ancestorNodeOnLeft;
}
TreeNode ancestorNodeOnRight = lowestCommonAncestor(root.right, p, q);
if (ancestorNodeOnRight != null && ancestorNodeOnRight.val != p.val
&& ancestorNodeOnRight.val != q.val) {
return ancestorNodeOnRight;
}
if (ancestorNodeOnLeft != null && ancestorNodeOnRight != null) {
return root;
}
if (ancestorNodeOnLeft != null) {
return ancestorNodeOnLeft;
}
if (ancestorNodeOnRight != null) {
return ancestorNodeOnRight;
}
return null;
}
}
先检测是否是p或q。是则停止向下遍历，改为向上归併。
再在左子树中搜寻，若找到公共祖先则直接返回。
再在右子树中搜寻，若找到公共祖先则直接返回。
再然后，检测当前节点是否为公共祖先。
复杂度分析
时间复杂度
本演算法只遍历了一次二叉树，时间复杂度为。
空间复杂度
空间复杂度为。