java - Java中递归的最低公共(public)祖先

Question

我在leetcode中找到了java中最低公共(public)祖先问题的解决方案。换句话说，问题是找到 p 和 q 的最低共同祖先，并且 BST 的根为根。这是我的代码。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left != null && right != null ? root : left == null?right :left;

    }

虽然这适用于大多数情况，但如果树是这样的并且问题是 lowerCommonAncestor(1, 2, 3) 或 2 和 3 的最低公共(public)祖先，其中 root == 1;

1 -> 2 -> 3

那么在我看来，这个解决方案将提供的答案是2，这是因为递归之后

left = null
right = 2

而实际答案是 1。

但是这个解决方案有效。有人可以帮助我理解我在这里出了什么问题吗？

Answer 1

遵循逻辑:

lowestCommonAncestor(root=1, p=2, q=3):
    if (root == null || root == p || root == q) return root;
    //     false           false        false

    left = lowestCommonAncestor(2, 2, 3):
               if (root == null || root == p || root == q) return root
               //     false            true                return 2

    right = lowestCommonAncestor(null, 2, 3):
                if (root == null || root == p || root == q) return root;
                //      true                                return null

    return left != null && right != null ? root : left == null ? right : left;
    //         true        false                     false             : 2

结果:2

遵循代码的最简单方法是使用调试器。