Easy Understand Java Recursive Solution with Explanation


  • 0
    M

    The basic idea is to recursively traversal the tree and return how many targeted nodes haven been visited. If find both nodes, add current node to a list. After finish traversal, return the first node in the list, that's the LCA.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> ans = new LinkedList<TreeNode>();
    	LCAHelper(root, p, q, ans);
    	return ans.getFirst();
    
    }
       
    private int LCAHelper(TreeNode root, TreeNode p, TreeNode q,
    		LinkedList<TreeNode> ans) {
        if (root == null)
    		return 0;
    	int temp = LCAHelper(root.left, p, q, ans)
    			+ LCAHelper(root.right, p, q, ans);  //return how many targets contained by current node's children
    
    	if (root == q || root == p) { //if the current node is one of our target
    		if (temp == 1) // if already found another target, add current node.
    			ans.add(root);
    		return temp + 1;
    	} else {
    		if (temp == 2) 
    			ans.add(root);
    		return temp;
    	}
    
    }

Log in to reply
 

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