Intuitive Java Recursive Solution


  • 0
    public class Solution {
        
        class Tuple {
            TreeNode ancestor;
            int status; // 00,10,01,11
        }
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return helper(root, p, q).ancestor;
        }
        
        public Tuple helper(TreeNode root, TreeNode p, TreeNode q) {
            Tuple res = new Tuple();
            if(root==null)
                return res;
                
            if(root==p)
                res.status |= 2;
            else if(root==q)
                res.status |= 1;
            
            Tuple leftRes = helper(root.left, p, q);
            if(leftRes.ancestor!=null)
                return leftRes;
            Tuple rightRes = helper(root.right, p, q);
            if(rightRes.ancestor!=null)
                return rightRes;
           
            res.status |= rightRes.status;
            res.status |= leftRes.status;
            
            if(res.status==3)
                res.ancestor = root;
    
            return res;
        }
    }

Log in to reply
 

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