二叉树最近公共祖先问题

一、问题定义

最近公共祖先（LCA）的定义

根据百度百科，对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

示例

给定二叉树：root = [3,5,1,6,2,0,8,null,null,7,4]，其结构如下：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

例如：

• 节点 5 和 1 的最近公共祖先是 3。
• 节点 5 和 4 的最近公共祖先是 5（因为 5 是 4 的祖先）。

二、问题分析

公共祖先满足的特征

1. 直接祖先：如果 p 是 q 的孩子，则 q 是祖先，反之亦然。
2. 分叉点：如果 p 和 q 分别在当前节点的左右子树中，则当前节点是祖先。

三种情况的解决方案

情况 1：二叉搜索树（BST）

利用 BST 的特性（左子树节点值 < 根节点值 < 右子树节点值），可以通过比较节点值来确定搜索方向：

• 如果一个比当前节点小，一个比当前节点大：当前节点就是最近公共祖先。
• 如果都比当前节点小：递归到左子树中查找。
• 如果都比当前节点大：递归到右子树中查找。

代码实现：

// 二叉搜索树的最近公共祖先TreeNode*lowestCommonAncestorBST(TreeNode*root,TreeNode*p,TreeNode*q){if(root==nullptr)returnnullptr;if(p->val<root->val&&q->val<root->val){// 都在左子树returnlowestCommonAncestorBST(root->left,p,q);}elseif(p->val>root->val&&q->val>root->val){// 都在右子树returnlowestCommonAncestorBST(root->right,p,q);}else{// 一个在左，一个在右，或其中一个是根节点returnroot;}}

情况 2：三叉链（每个节点有父指针）

类似于链表找交点问题，利用路径长度差来找到公共祖先：

1. 计算两个节点到根节点的距离。
2. 让距离较远的节点先向上移动，直到两者距离相同。
3. 两个节点同时向上移动，直到相遇，相遇点即为最近公共祖先。

代码实现：

// 三叉链的最近公共祖先（每个节点有父指针）TreeNode*lowestCommonAncestorTrident(TreeNode*p,TreeNode*q){if(p==nullptr||q==nullptr)returnnullptr;// 计算两个节点到根节点的距离intdepthP=getDepth(p);intdepthQ=getDepth(q);// 让较深的节点先向上移动while(depthP>depthQ){p=p->parent;depthP--;}while(depthQ>depthP){q=q->parent;depthQ--;}// 同时向上移动，直到相遇while(p!=q){p=p->parent;q=q->parent;}returnp;}// 辅助函数：计算节点到根节点的距离intgetDepth(TreeNode*node){intdepth=0;while(node){node=node->parent;depth++;}returndepth;}

情况 3：普通二叉树

对于普通二叉树，需要递归遍历左右子树，判断 p 和 q 的位置：

• 如果当前节点是 p 或 q：返回当前节点（因为一个节点是它自己的祖先）。
• 如果左子树和右子树都返回非空：当前节点是最近公共祖先（p 和 q 分别在左右子树）。
• 如果只有左子树返回非空：最近公共祖先在左子树。
• 如果只有右子树返回非空：最近公共祖先在右子树。

代码实现：

// 普通二叉树的最近公共祖先TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root==nullptr||root==p||root==q){returnroot;}// 递归左子树TreeNode*left=lowestCommonAncestor(root->left,p,q);// 递归右子树TreeNode*right=lowestCommonAncestor(root->right,p,q);if(left!=nullptr&&right!=nullptr){// p 和 q 分别在左右子树returnroot;}elseif(left!=nullptr){// 都在左子树returnleft;}else{// 都在右子树returnright;}}

三、时间复杂度分析

• 二叉搜索树：利用其有序性，每次比较都能排除一半的节点，时间复杂度为 O(log n)。
• 三叉链：需要计算深度，最坏情况下遍历整个树，时间复杂度为 O(n)。
• 普通二叉树：需要遍历所有节点，时间复杂度为 O(n)。

四、总结

• 二叉搜索树：利用其有序性，通过比较节点值快速定位。
• 三叉链：利用父指针，通过路径长度差找到交点。
• 普通二叉树：通过递归遍历，判断节点位置关系。

相关链接：

• LeetCode 236. 二叉树的最近公共祖先
• LeetCode 235. 二叉搜索树的最近公共祖先