AcWing 88. 树中两个结点的最低公共祖先---递归
原题链接
中等
作者:
巨鹿噜噜噜路
,
2020-06-01 23:37:49
,
所有人可见
,
阅读 504
C++ 代码
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);
//本身p/q节点就是公共父节点
if(left == NULL || right == NULL) {
if(left) return left;
else return right;
}
//左右子树都找到了该节点
return root;
}
};