Java for LeetCode 226 Lowest Common Ancestor of a Binary Tree

問題解決の考え方:
各ノードを巡る経路を見つけ、経路からLCAを算出すればよい

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == p || root == q)
			return root;
		List pList = new ArrayList<TreeNode>(), qList = new ArrayList<TreeNode>();
		getPath(root,p,pList);
		getPath(root,q,qList);
		for(int i=0;i<Math.min(pList.size(), qList.size());i++){
			if(pList.get(i)!=qList.get(i))
				return (TreeNode) pList.get(i-1);
		}
		return (TreeNode) pList.get(Math.min(pList.size(), qList.size())-1);
	}

	private boolean getPath(TreeNode root, TreeNode p, List<TreeNode> path) {
		path.add(root);
		if (root == p)
			return true;
		if (root.left != null) {
			if (getPath(root.left, p, path))
				return true;
			path.remove(path.size() - 1);
		}
		if (root.right != null) {
			if (getPath(root.right, p, path))
				return true;
			path.remove(path.size() - 1);
		}
		return false;
	}
}