Easy Understand Java Recursive Solution with Explanation

  • 0

    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.
    		return temp + 1;
    	} else {
    		if (temp == 2) 
    		return temp;

Log in to reply

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