Lowest Common Ancestor II

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes. The lowest common ancestor is the node with largest depth which is the ancestor of both nodes. Return null if LCA does not exist.

node A or node B may not exist in tree.Have you met this question in a real interview? YesProblem Correction

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Related Problems

space o(n),time o(n) n is tree' s level

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */


public class Solution {
    /*
     * @param root: The root of the tree
     * @param A: node in the tree
     * @param B: node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        // write your code here
        
        List<ParentTreeNode> listA = getPath(A);
        List<ParentTreeNode> listB = getPath(B);
        
        int indexA = listA.size()-1;
        int indexB = listB.size()-1;
        ParentTreeNode res = root;
        while(indexA >= 0 && indexB >= 0){
            if(listA.get(indexA) != listB.get(indexB)){
                break;
            }
            
            res = listA.get(indexA);
            indexA--;
            indexB--;
        }
        
        return res;
    }
    
    public List<ParentTreeNode> getPath(ParentTreeNode node){
        List<ParentTreeNode> list = new ArrayList<>();
        
        while(node != null){
            list.add(node);
            
            node = node.parent;
        }
        
        return list;
    }
}