剑指 Offer 68 - II. 二叉树的最近公共祖先
力扣题目链接[1]
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1:
代码语言：javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
代码语言：javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
「说明:」
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
思路：
本题是昨天题解的升级版。昨天的题目中，规定了是二叉搜索树。今天的题目没有该规定，因此无法使用二叉搜索树的特征来进行题解。
递归
本题采用递归进行题解。
如果root是节点p和q的最近公共祖先，那么会出现三种情况：
- p、q 节点分布在 root 的左右子树中。
- p 就是 root 节点，且 q 在 root 的左右子树中。
- q 就是 root 节点，且 p 在 root 的左右子树中。
首先看下递归的终止条件：
- 当 root 节点为空时，直接返回 root 节点。
- 当 root 节点就是 p 或者 q 节点时，直接返回 root 节点，因为 root 节点就是最近公共祖先。
递归的主流程为分别递归左子树和右子树，并缓存结果为left或right。
结果分为以下四种情况：
- 当
left和right都为空，意味着p和q不存在于root的左子树和右子树，直接返回null。 - 当
left和right都不为空，意味着p和q分别位于root的左右子树，那么此时root就是最近公共节点，直接返回root。 - 当
left为空，right不为空时，意味着p和q都在右子树中，直接返回right。 - 当
left不为空，right为空时，意味着p和q都在左子树中，直接返回left。
那么就可以写出如下代码：
代码语言：javascript复制/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if (!root || root === p || root === q) return root; // 递归终止条件
let left = lowestCommonAncestor(root.left, p, q); // 缓存左子树结果
let right = lowestCommonAncestor(root.right, p, q); // 缓存右子树结果
if (!left) return right; // 分别是上面的四种情况
if (!right) return left;
return root;
};
- 时间复杂度 O(n)。
- 空间复杂度 O(n)。
分析：
不难发现，上面分析的第一种情况可以归置到第三和第四中情况当中。
因此最终的代码中不需要再进行第一种情况的判断。
总结
本题与上一题的区别就是无法直接使用二叉搜索树的结论进行题解。所以要分别判断左子树和右子树的情况。
复杂度方面，最坏情况下，需要遍历二叉树的所有节点，因此时间复杂度是O(n) 。而递归的函数调用栈最多也需要O(n) 的空间。
参考资料
[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57euni/
