Search-based Recursive Solution using Memorization


  • 1
    public class Solution {
        Map<TreeNode,Boolean> pMap = new HashMap<TreeNode,Boolean>();
        Map<TreeNode,Boolean> qMap = new HashMap<TreeNode,Boolean>();
        
        public boolean searchNode(TreeNode root, TreeNode node, boolean isP) {
            if(root==null)
                return false;
            if(root==node)
                return true;
            Map<TreeNode,Boolean> map = isP ? pMap : qMap;
            if(map.containsKey(root))
                return map.get(root);
            boolean ret = searchNode(root.left,node,isP) || searchNode(root.right,node,isP);
            map.put(root,ret);
            return ret;
        }
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null)
                return null;
            if(root==p && searchNode(p,q,false))
                return p;
            if(root==q && searchNode(q,p,true))
                return q;
            boolean pInLeft = searchNode(root.left,p,true);
            boolean qInRight = searchNode(root.right,q,false);
            if(pInLeft&&qInRight)
                return root;
            boolean pInRight = searchNode(root.right,p,true);
            boolean qInLeft = searchNode(root.left,q,false);
            if(pInRight&&qInLeft)
                return root;
            if(pInLeft&&qInLeft)
                return lowestCommonAncestor(root.left,p,q);
            if(pInRight&&qInRight)
                return lowestCommonAncestor(root.right,p,q);
            return null; // this cannot happen cause p and q must exist in the tree
        }
    }

  • 0
    U

    My answer was on the same thinking line as you! But not the optimal one!


Log in to reply
 

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