Java solution with our without BST property


  • 0
    L

    This solution has two methods:

    1. That uses BST property
    2. That doesn't use BST property
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null) {
                return null;
            }
            int low = Math.min(p.val,q.val);
            int high = Math.max(p.val,q.val);
    
            while(root.val<low || root.val>high) {
                while(root.val<low) {
                    root = root.right;
                }
                while(root.val>high) {
                    root = root.left;
                }
            }
    
            return root;
        }
    
       /**
         * Doesn't use BST property so use it with a regular binary tree. 
         */
        public TreeNode lowestCommonAncestorNonBST(TreeNode root, TreeNode p, TreeNode q) {
            if(p == root || q == root) {
                return root;
            }
            
            if(root==null) {
                return null;
            }
            
            
            TreeNode left = lowestCommonAncestorNonBST(root.left,p,q);
            TreeNode right = lowestCommonAncestorNonBST(root.right,p,q);
            if(left==null && right==null) {
                //no LCA found yet.
                return null;
            }
            else if(left!=null && right!=null) {
                //both not null; the current root is the LCA.
                return root;
            }
    
            //Either or the values is an LCA.
            return left==null?right:left;
    
        }
    

Log in to reply
 

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