Share my 5-line Java code with brief explanation


  • 12
    M
    /*
        -- 从上向下搜索, 遇到p或q或null, return之
        -- 回溯过程中, (1).左return != null且右return != null (即左p右q或左q右p), 说明current root是LCA, return之;
                      (2).左右谁不为null就向上return谁 (即p或q, 或null).
    */ 
    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;
        }
    }

  • 0
    D

    How about the case that p or q is not in the tree?


  • 0
    M

    honestly, it is not considered here in the code. while it happens to return the right result(null) when "both p and q are not in the tree", it is wrong when "one of them is in the tree and the other is not". we have to assume that "both p and q are in the tree", otherwise a sanity check may be needed before this code. any good idea?


  • 0
    F

    Can you please explain how this works?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.