Java Solution, Easy and Concise enough to be understood


  • 0
    X

    The main idea is to check three situations:

    1.p and q are on the different sides of the root, then return root

    2.p and q both are on the left side of root, search recursively until No. 1 happens Or p or q equals the root

    3.p and q both are on the right side of root, search recursively until No. 1 happens Or p or q equals the root

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return null;
            else if(Math.max(p.val, q.val) < root.val){
                if(root.left == p) return p;
                else if(root.left == q) return q;
                else return lowestCommonAncestor(root.left, p, q);
            }
            else if(Math.min(p.val, q.val) > root.val){
                if(root.right == p) return p;
                else if(root.left == q) return q;
                else return lowestCommonAncestor(root.right, p, q);
            }
            else return root;
        }
    }

  • 0
    M

    More than four lines can be simply deleted and it will still work.


Log in to reply
 

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