236. 二叉树的最近公共祖先
3 min
题目
解法：递归后序
思路
采用后序遍历递归策略，通过判断左右子树是否包含目标节点来确定最近公共祖先。
该方法正确性的关键在于递归的不变性——对于任意节点，若其左子树包含p或q中的一个，右子树包含另一个，则该节点必为最近公共祖先；若仅一侧包含两个节点，则返回该侧找到的节点；若当前节点本身就是p或q，则直接返回。这种自底向上的搜索方式确保首次同时找到p和q的节点即为深度最大的公共祖先。
- Step 1: 若当前节点为空或是p/q之一，直接返回当前节点
- Step 2: 递归遍历左子树，查找p和q
- Step 3: 递归遍历右子树，查找p和q
- Step 4: 若左右子树均找到非空节点，说明当前节点是最近公共祖先
- Step 5: 否则返回非空的左或右子树结果
复杂度
- 时间复杂度: ，其中n为节点总数，每个节点仅访问一次
- 空间复杂度: ，其中h为树的高度，递归栈空间消耗
代码
/**
* 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 == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) {
return root;
}
return left != nullptr ? 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 == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) {
return root;
}
return left != nullptr ? left : right;
}
};