剑指offer 76- 树中两个结点的最低公共祖先
给出一个二叉树，输入两个树节点，求它们的最低公共祖先。
一个树节点的祖先节点包括它本身。
注意：
输入的二叉树不为空；
输入的两个节点一定不为空，且是二叉树中的节点；
样例
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \q
12 2
/ \
6 4
1. 如果输入的树节点为2和12，则输出的最低公共祖先为树节点8。
2. 如果输入的树节点为2和6，则输出的最低公共祖先为树节点2。
分析：
算法一：递归
若 rootrootroot 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
- p 和 q在 root 的子树中，且分列 root的 异侧（即分别在左、右子树中）；
- p=root ，且 q 在 root 的左或右子树中；
- q=root ，且 p 在 root 的左或右子树中；
递归解析：
-
终止条件：
当越过叶节点，则直接返回 null；
当 root 等于 p,q ，则直接返回 root ； -
递推过程：
递归左子节点，返回值记为 left ；
递归右子节点，返回值记为 right ； -
返回值： 根据 left 和 right ，可展开为四种情况；
当 left 和 right同时为空 ：说明 root的左 / 右子树中都不包含 p,q ，返回 null ；
当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
p,q 其中一个在 root的 右子树 中，此时 right 指向 p（假设为 p ）；
p,q 两节点都在 roo 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
当 left不为空 ， right 为空 ：同理；
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root==p || root==q) return root;//递归终止条件
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;//两个节点分别位于左子树和右子树
if(!left) return right;//左子树中两个节点都找不到
return left;//右子树中两个节点都找不到
}
};
复杂度分析
-
时间复杂度：O(N)，其中 NNN 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
-
空间复杂度：O(N) ，其中 NNN 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 NNN，因此空间复杂度为 O(N)。
算法二：存储父节点
我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先。
复杂度分析
-
时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。
-
空间复杂度：O(N)，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N)的空间复杂度，因此最后总的空间复杂度为 O(N)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*, TreeNode*> father;
unordered_map<TreeNode*, bool> vis;
void dfs(TreeNode* root) {
if(root->left) father[root->left] = root, dfs(root->left);
if(root->right) father[root->right] = root, dfs(root->right);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
father[root] = nullptr;
dfs(root);
while(p) vis[p] = true, p = father[p];
while(q) {
if(vis[q]) return q;
q = father[q];
}
return nullptr;
}
};
