Lastest Common Ancester

Find the Latest Common Ancestor of two TreeNode.
For Example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

 The LCA of 3 and 4 is 2. 5 and 6 is 5.

	package leetcode.tree;
	import java.util.ArrayList;
	public class LatestCommonAncestor {
	/**
	* Thought:
	* 1. Get parent node until root.
	* 2. find the node1 and node2 in left and right subtree. if found, return node and go up. if not found,
	* that means in the another(left / right) tree;
	* 3. Conclude scenario two nodes in one line, will return the first directly.
	*/
	public TreeNode lastCommonAncestor(TreeNode node1, TreeNode node2) {
	if (node1 == null || node2 == null) {
	return null;
	}
	TreeNode root = getRoot(node1);
	return getChild(root, node1, node2);
	}
	private TreeNode getRoot(TreeNode node) {
	while (node.parent != null) {
	node = node.parent;
	}
	return node;
	}
	public TreeNode getChild(TreeNode root, TreeNode node1, TreeNode node2) {
	if (root == null || root == node1 || root == node2) {
	return root;
	}
	// Divide
	TreeNode left = getChild(root.left, node1, node2);
	TreeNode right = getChild(root.right, node1, node2);
	// Conquer
	if (left != null && right != null) {
	return root;
	}
	if (left != null) {
	return left;
	}
	if (right != null) {
	return right;
	}
	return null;
	}
	/**
	* Thought: very straightforwards
	* 1. getPath2Root --> get every node's Path to Root and saved as a list.
	* 2. iterative and find out when they are different which means that node is their latest common ancestor
	*
	* Take care:
	* 1. iterative must begin from end to start. if reverse, as length may be different, can find the common one.
	* 2. if two nodes are on one line, will not return in for, then i or j == -1, return i+1 last one. which will be common.
	*
	*/
	public TreeNode lastCommonAncestor2(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);
	}
	public ArrayList<TreeNode> getPath2Root(TreeNode node) {
	ArrayList<TreeNode> list = new ArrayList<TreeNode>();
	while (node != null) {
	list.add(node);
	node = node.parent;
	}
	return list;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode parent;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw LatestCommonAncestor.java hosted with ❤ by GitHub