题目
给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。
- 对于该题的最近的公共先人定义: 对于有根树 T 的两个节点 p、q，最近公共先人 LCA(T,p,q) 示意一个节点 x，满足 x 是 p 和 q 的先人且 x 的深度尽可能大。在这里，一个节点也能够是它本人的先人.
- 二叉搜寻树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 所有节点的值都是惟一的。
- p、q 为不同节点且均存在于给定的二叉搜寻树中。
数据范畴: 3<= 节点总数 <=10000 0<= 节点值 <=10000
如果给定以下搜寻二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:
示例 1
输出：{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值：7
阐明：节点 1 和 节点 12 的最近公共先人是 7 示例 2
输出：{7,1,12,0,4,11,14,#,#,3,5},12,11
返回值：12
阐明：因为一个节点也能够是它本人的先人. 所以输入 12思路
利用二叉搜寻树的性质：对于某一个节点若是 p 与 q 都小于这个这个节点值，阐明 p、q 都在这个节点的左子树，而最近的公共先人也肯定在这个节点的左子树；若是 p 与 q 都大于这个节点，阐明 p、q 都在这个节点的右子树，而最近的公共先人也肯定在这个节点的右子树。而若是对于某个节点，p 与 q 的值一个大于等于节点值，一个小于等于节点值，阐明它们散布在该节点的两边，而这个节点就是最近的公共先人。所以就能够用递归的办法来解决这个问题。
解答代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* @param root TreeNode 类
* @param p int 整型
* @param q int 整型
* @return int 整型
*/
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if (root == nullptr) {return -1;}
int small = p < q ? p : q;
int big = p > q ? p : q;
if (root->val >= small && root->val <= big) {
// root 的值在两个数字之间，阐明它就是要找的公共先人
return root->val;
} else if (root->val > small && root->val > big) {
// root 的值大于两个数字，须要到左子树去找
return lowestCommonAncestor(root->left, small, big);
} else {
// root 的值小于两个数字，须要到右子树去找
return lowestCommonAncestor(root->right, small, big);
}
}
};