LCA-- from graph angle, easy understanding


  • 0
    W
    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode,TreeNode> Dict = new HashMap<TreeNode,TreeNode>();
    	Stack<TreeNode> stk = new Stack<TreeNode>();
    	stk.push(root);
    	Dict.put(root, null);
    	while(!Dict.containsKey(p) || !Dict.containsKey(q)){
    		TreeNode item = stk.pop();
    		if(item.left!=null){
    			stk.push(item.left);
    			Dict.put(item.left,item);
    		}
    		if(item.right!=null){
    			stk.push(item.right);
    			Dict.put(item.right, item);
    		}
    
    	}
    	
    	Set<TreeNode> path = new HashSet<TreeNode>();
    	while(p!=null){
    		path.add(p);
    		p = Dict.get(p);
    		
    	}
    	while(!path.contains(q)){
    		q = Dict.get(q);
    	}
    	return q;
    
    }
    

    }


Log in to reply
 

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