如何使用Java实现二叉树的最低共同祖先？

Question

我遇到了以下实现并花了一些时间,但仍然无法掌握这个想法.有人可以逐行解释它在做什么吗？我只是不明白在什么时候它可以决定一个节点是一个祖先.

谢谢

public class Solution {
    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);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}

Answer 1

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // root == null (no root no LCA)
    // root == p || root == q (if either p or q is the root then root is LCA)
    if(root == null || root == p || root == q)  return root;
    //get the LCA of p and q in left sub tree
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    //get the LCA of p and q in right sub tree
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // if one of p or q is in left subtree and another is in the right subtree, 
    //then the root is the LCA
    if(left != null && right != null)   return root;
    // if left is not null, left is LCA, else right is LCA 
    return left != null ? left : right;
}