题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
递归
三种情况：
- 当前结点值小于q，p，就在当前结点的左子树寻找最近公共祖先。
- 当前结点值大于q，p，就在当前结点的右子树寻找最近公共祖先。
- p，q 包含了当前结点值，即 q<=val<=p，或 q>=val>=p，那么公共祖先就是该节点。
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if (p > root->val && q > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else if (p < root->val && q < root->val) {
return lowestCommonAncestor(root->left, p, q);
}
return root->val;
}
};
投递卓越教育等公司9个岗位 >
