Java not-so-short but Crystal Clear Solution (with a condensed version and explanations)


  • 1
    Y

    My solution might not be the shortest, but hopefully easier to understand. I also included a condensed version from another post and will explain how my solution can be shortened into a more concise one.

    My solution:
    I used a bottom up approach. Use recursion to traverse the tree to bottom. If we haven't found any of p or q, return null. If we have found p or q in the subtree, return it. If we know p and q are in the left or right subtrees respectively, we have found the lowest common ancestor, and we return it all the way to the top. There are a total of 6 cases I considered (marked in code as comment).

    1. TreeNode p and q are in left and right (or right and left) subtree, respectively. This problem assumes no duplication of TreeNode p or q, so the current root must be the lowest common ancestor.

    2. Either p or q is found in either left or right subtree, and root is the other we are looking for.

    3. We can't find both p and q, but current root is either p or q.

    4. We can't find any new information about p or q, but the left subtree contains p or q. This can actually happen in two cases:
      a) We have found one of p and q, but haven't found the other
      b) We have found the lowest common ancestor of p and q, but p or q itself happens to be the lowest common ancestor.

    5. Same as 4, no new information, but right subtree contains p or q.

    6. None of the above conditions were met. This can be caused by:
      a) We have found the lowest common ancestor (which may not be equal to p or q). One of left and right is the common ancestor, and the other is null.
      b) We haven't found any of p and q yet (both left and right are null).
      In this case, we can simply return the non-null TreeNode. If they are both null, return null. This can be shortened to one line.

    Basically I draw a subtree that we meet during a recursive step and figured out the cases above.
    x
    / \
    yz

    This problem also assumes that p and q must exist in the tree, not sure if my code works if existence is not guaranteed.

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return root;
            // recursive calls
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // bottom-up backtracing
            // 1
            if ((left == p && right == q) || (left == q && right == p)) {
                return root;
            }
            // 2
            if ((left == p && root == q) || (left == q && root == p) || (right == p && root == q) || (right == q && root == p)) {
                return root;
            }
            // 3
            if (root == p || root == q) {
                return root;
            }
            // 4
            if (left == p || left == q) {
                return left;
            }
            // 5
            if (right == p || right == q) {
                return right;
            }
            // 6
            return left == null ? right : left;
        }
    }
    

    This amazong 10-line solution is taken from: https://discuss.leetcode.com/topic/18738/10-line-java-solution-solved-in-one-traversal
    My solution is a bit complex, but assuming (I think) both p and q exists in the tree, it can be shortened to this concise one.

    It also uses a bottom-up approach. Basically we recurse to traverse the tree. When we have found p or q, return it all the way till we find both p and q in separate subtrees, where the current root is the LCA. Then return it.

    // condensed version
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            
            TreeNode l = lowestCommonAncestor(root.left,p,q);
            TreeNode r = lowestCommonAncestor(root.right,p,q);
            
            if(root == p || root == q){
                return root;
            }
            
            if(l != null && r != null){
                return root;
            }
            
            return l != null ? l:r;
        }
    }
    ``

Log in to reply
 

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