题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
http://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
-
空树没有最近公共祖先
-
如果p和q两个数一个大于根结点的值,一个小于根结点的值,那么就分属左右两边,根结点即为最近公共祖先。
-
如果p和q两个数都小于根结点的值,那么就都在根结点的左边,那么把根结点的左孩子结点当作根结点用递归继续找。
-
如果p和q两个数都大于根结点的值,那么就都在根结点的右边,那么把根结点的右孩子结点当作根结点用递归继续找。
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
if(root == NULL)
return -1;
if((p <= root->val && q >= root->val) || (p >= root->val && q <= root->val) )
return root->val;
else if(p<=root->val && q<=root->val)
return lowestCommonAncestor(root->left, p, q);
else //if(p>=root->val && q>=root->val) //最后一个用else不要用else if
return lowestCommonAncestor(root->right, p, q);
}