Keep it simple and stupid - divide and conquer solution in Java


  • 0
    H
    class Solution {
        class ResultType{
            TreeNode lca = null;
            boolean pFound = false;
            boolean qFound = false;
            public ResultType(TreeNode lca, boolean pFound, boolean qFound){
                this.lca = lca;
                this.pFound = pFound;
                this.qFound = qFound;
            }
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return helper(root, p, q).lca;
        }
        private ResultType helper(TreeNode root, TreeNode p, TreeNode q){
            if(root == null) return new ResultType(null, false, false);
            ResultType left = helper(root.left, p, q);
            ResultType right = helper(root.right, p, q);
            if(left.lca != null) return new ResultType(left.lca, true, true);
            if(right.lca != null) return new ResultType(right.lca, true, true);
            if(left.pFound&&right.qFound || left.qFound&&right.pFound){
                return new ResultType(root, true, true);
            }
            if(left.pFound&&root==q || right.pFound&&root==q
               || left.qFound&&root==p || right.qFound&&root==p){
                return new ResultType(root, true, true);
            }
            return new ResultType(null, left.pFound||right.pFound||root==p, 
                                  left.qFound||right.qFound||root==q);
        }
    }
    

Log in to reply
 

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