# Search-based Recursive Solution using Memorization

• ``````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
}
}``````

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

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