题目


给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。

  • 对于该题的最近的公共先人定义:对于有根树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);        }    }};