题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
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); }
投递快手等公司10个岗位