Leetcode: Lowest Common Ancestor of a Binary Tree

http://buttercola.blogspot.com/2014/11/facebook-lca-without-parent-pointer.html

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode[] level = new TreeNode[100000];
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        
        List<TreeNode> path1 = new ArrayList<TreeNode>();
        List<TreeNode> path2 = new ArrayList<TreeNode>();
        
        if (!verticalTraverse(root, p, path1, 0)) {
            return null;
        }
        
        if (!verticalTraverse(root, q, path2, 0)) {
            return null;
        }
        
        TreeNode result = null;
        int i = 0;
        int j = 0;
        while (i < path1.size() && j < path2.size()) {
            if (path1.get(i) != path2.get(j)) {
                return path1.get(i - 1);
            }
            i++;
            j++;
        }
        
        return path1.get(i - 1);
    }
    
    private boolean verticalTraverse(TreeNode root, TreeNode p, List<TreeNode> path, int i) {
        if (root == null) {
            return false;
        }
        
        level[i] = root;
        
        if (root == p) {
            for (int j = 0; j <= i; j++) {
                path.add(level[j]);
            }
            return true;
        }
        
        if (root.left != null && verticalTraverse(root.left, p, path, i + 1)) {
            return true;
        }
        
        if (root.right != null && verticalTraverse(root.right, p, path, i + 1)) {
            return true;
        }
        
        return false;
    }
}

A neat Divide-and-Conquer solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // Divide
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        }
        
        if (left != null) {
            return left;
        }
        
        if (right != null) {
            return right;
        }
        
        return null;
    }
}

Update on 11/5/15:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        
        List<TreeNode> list1 = new ArrayList<>();
        List<TreeNode> list2 = new ArrayList<>();
        
        if (!getPath(root, p, list1)) {
            return null;
        }
        
        if (!getPath(root, q, list2)) {
            return null;
        }
        
        int i = 0;
        for (i = 0; i < list1.size() && i < list2.size(); i++) {
            if (list1.get(i) != list2.get(i)) {
                return list1.get(i - 1);
            }
        }
        
        return list1.get(i - 1);
    }
    
    private boolean getPath(TreeNode root, TreeNode target, List<TreeNode> result) {
        if (root == null) {
            return false;
        }
        
        result.add(root);
        
        if (root == target) {
            return true;
        }
        
        if (root.left != null) {
            if (getPath(root.left, target, result)) {
                return true; 
            } else {
                result.remove(result.size() - 1);
            }
        }
        
        if (root.right != null) {
            if (getPath(root.right, target, result)) {
                return true;
            } else {
                result.remove(result.size() - 1);
            }
        }
        
        return false;
    }
}

Follow-up:
What if there is a pointer to the parent?
Method 1: traditional method by using extra space

public class Solution {
    private ArrayList<TreeNode> getPath2Root(TreeNode node) {
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        while (node != null) {
            list.add(node);
            node = node.parent;
        }
        return list;
    }
    public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) {
        ArrayList<TreeNode> list1 = getPath2Root(node1);
        ArrayList<TreeNode> list2 = getPath2Root(node2);
        
        int i, j;
        for (i = list1.size() - 1, j = list2.size() - 1; 
          i >= 0 && j >= 0; i--, j--) {
            if (list1.get(i) != list2.get(j)) {
                return list1.get(i).parent;
            }
        }
        return list1.get(i+1);
    }
}

Method 2: without using extra space

public Node findLCA(Node root, Node p, Node q) {
   if (root == null || p == null || q == null) return null;
   int depth1 = getDepth(root, p);
   int depth2 = getDepth(root, q);
   if (depth1 > depth2) {
      swap(depth1, depth2);
      swap(p, q);
   }
   for (int i = 0; i < depth1 - depth2; i++) {
      q = q.parent;
   }
   while (p) {
      if (p == q) return p;
      p = p.parent;
      q = q.parent;
   }
   return null;
}

public int getDepth(Node root, Node n) {
   if (root == null || n == null) return null;
   int depth = 0;
   while (root != n) {
      depth++;
      n = n.parent;
   }
   return depth;
}

public void swap(Object<T> a, Object<T> b) {
   Object<T> tmp = a;
   a = b;
   b = tmp;
}