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

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(
    一个节点也可以是它自己的祖先)。”

    例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

    1. 6
    2. / \
    3. 2 8
    4. / \ / \
    5. 0 4 7 9
    6. / \
    7. 3 5

    示例 1:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

    示例 2:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

    说明:
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

    二叉搜索树的特点:

    • 左子树的值都比根节点的值小
    • 右子树的值都比根节点的值大

    那么如果需要搜索 p 和 q 的公共祖先:

    • 假设 p 和 q 的值都比根节点的值小,那么需要去左子树查找
    • 假设 p 和 q 的值都比根节点的值大,那么需要去右子树查找
    • 假设 p 和 q 的值一个比根节点的值大,一个比根节点的值小,那么根节点就是公共祖先了
    • 假设 p 和 q 的值有一个等于根节点值,那么根节点就是公共祖先了

    第一版算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. if (p.val == root.val || q.val == root.val) {
    3. return root;
    4. }
    5. if ((p.val < root.val && q.val > root.val) || (p.val > root.val && q.val < root.val)) {
    6. return root;
    7. }
    8. if (p.val < root.val && q.val < root.val) {
    9. // 继续左子树中查找
    10. }
    11. if (p.val > root.val && q.val > root.val) {
    12. // 继续右子树中查找
    13. }
    14. return null;
    15. }

    为了可以在左子树和右子树中不断的找,需要可以不断循环,需要有个临时对象用于遍历
    第二版算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. TreeNode target = root;
    3. if (p.val == target.val || q.val == target.val) {
    4. return target;
    5. }
    6. if ((p.val < target.val && q.val > target.val) || (p.val > target.val && q.val < target.val)) {
    7. return target;
    8. }
    9. if (p.val < target.val && q.val < target.val) {
    10. // 继续左子树中查找
    11. }
    12. if (p.val > target.val && q.val > target.val) {
    13. // 继续右子树中查找
    14. }
    15. return null;
    16. }

    加入 while 循环
    第三版算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. TreeNode target = root;
    3. while(true) {
    4. if (p.val == target.val || q.val == target.val) {
    5. return target;
    6. }
    7. if ((p.val < target.val && q.val > target.val) || (p.val > target.val && q.val < target.val)) {
    8. return target;
    9. }
    10. if (p.val < target.val && q.val < target.val) {
    11. // 继续左子树中查找
    12. }
    13. if (p.val > target.val && q.val > target.val) {
    14. // 继续右子树中查找
    15. }
    16. }
    17. return target;
    18. }

    while 循环内前两个分支条件重叠了,因为默认就是返回 target ,故可以省略
    第四版算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. TreeNode target = root;
    3. while(true) {
    4. if (p.val < target.val && q.val < target.val) {
    5. // 继续左子树中查找
    6. }
    7. if (p.val > target.val && q.val > target.val) {
    8. // 继续右子树中查找
    9. }
    10. }
    11. return target;
    12. }

    while 需要可以退出循环
    第五版算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. TreeNode target = root;
    3. while(true) {
    4. if (p.val < target.val && q.val < target.val) {
    5. // 继续左子树中查找
    6. } else if (p.val > target.val && q.val > target.val) {
    7. // 继续右子树中查找
    8. } else {
    9. break;
    10. }
    11. }
    12. return target;
    13. }

    最终完整算法:

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2. TreeNode target = root;
    3. while(true) {
    4. if (p.val < target.val && q.val < target.val) {
    5. // 继续左子树中查找
    6. target = target.left;
    7. } else if (p.val > target.val && q.val > target.val) {
    8. // 继续右子树中查找
    9. target = target.right;
    10. } else {
    11. break;
    12. }
    13. }
    14. return target;
    15. }