NC102：在二叉树中找到两个节点的最近公共祖先

解法1：递归
考虑两个结点的存在情况：

1. 一个节点为是另外一个节点的子或孙子节点，此时只要判断root节点等于其中一个节点即可；
2. 两个节点分属两支，此时两个节点都是root节点的子或孙结点，同时在root.left和root.right中各能找到一个节点；
3. 如果不属于以上两种情况，对root.left和root.right递归判断。

   public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return CommonAncestor(root, o1, o2).val;
    }
    public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root==null || root.val==o1 || root.val==o2){
            return root;
        }
        TreeNode left=CommonAncestor(root.left,o1,o2);
        TreeNode right=CommonAncestor(root.right,o1,o2);
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }

解法2：两个结点的路径
首先找到根节点到两个节点的路径，然后将其中一个路径加入到哈希表或者链表中，然后遍历另一个路径，在哈希表\链表中有相同的则返回即可

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        List<Integer> path1 = new ArrayList<>();
        List<Integer> path2 = new ArrayList<>();
        path1.add(root.val);
        getPath(root, o1, path1);
        path2.add(root.val);
        getPath(root, o2, path2);
        int res = 0;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1.get(i) == path2.get(i))
                res = path1.get(i);
            else
                break;
        }
        return res;
    }
    private boolean getPath(TreeNode root, int node, List<Integer> path) {
        if (root.val == node) 
            return true;
        if (root.left != null) {
            path.add(root.left.val);
            if (getPath(root.left, node, path)) 
                return true;
            else path.remove(path.size()-1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            if (getPath(root.right, node, path)) 
                return true;
            else 
                path.remove(path.size()-1);
        }
        return false;
    }