关于java:LeetCode235二叉搜索树的最近公共祖先

27次阅读

共计 1474 个字符，预计需要花费 4 分钟才能阅读完成。

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

百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法

首先，如果 p 或 q 是根节点，间接返回根节点。

如果 p 和 q 都不是根节点，则分以下几种状况解决：

如果 p 和 q 的值都小于 root 的值，则递归调用该办法 lowestCommonAncestor，入参为 root.left。

如果 p 和 q 的值都小于 root 的值，则递归调用该办法 lowestCommonAncestor，入参为 root.right。

如果 p 和 q 一个大于 root 的值，另一个小于 root 的值，则 p 和 q 的最近公共先人只可能是 root，所以间接返回 root。

public class LeetCode_235 {
    /**
     * 递归法
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果 p 或 q 是根节点，间接返回根节点
        if (p == root) {return p;}
        if (q == root) {return q;}
        if (p.val < root.val && q.val < root.val) {
            // 如果 p 和 q 的值都小于 root 的值，则递归调用该办法，入参为 root.left
            return lowestCommonAncestor(root.left, p, q);
        } else if (p.val > root.val && q.val > root.val) {
            // 如果 p 和 q 的值都大于 root 的值，则递归调用该办法，入参为 root.right
            return lowestCommonAncestor(root.right, p, q);
        } else {
            // 如果 p 和 q 一个大于 root 的值，另一个小于 root 的值，则 p 和 q 的最近公共先人只可能是 root，所以间接返回 root
            return root;
        }
    }

    public static void main(String[] args) {
        // 初始化一颗二叉搜寻树
        TreeNode root = new TreeNode(6);
        TreeNode node_2 = new TreeNode(2);
        TreeNode node_8 = new TreeNode(8);
        root.left = node_2;
        root.right = node_8;
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);

        // 调用办法，返回后果
        TreeNode result = lowestCommonAncestor(root, node_2, node_8);
        System.out.println(result.val);
    }
}