Leetcode 236.二叉树的最近共同祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

题解：
本题我最开始的思路是先分情况讨论，分为两种情况：

1. 其中一个结点是另一个结点的祖先，则返回结果是那个祖先结点
2. 两结点另有共同的祖先，需要找出最近的祖先
   但在后续找共同祖先的时候，又发现其实两种情况可以合并。找法为：找两结点都回溯到根节点的路径，再从根结点找两路径中相同的最后结点。

由于题中最后提示了所有结点值都不相同，其实这个思路可以优化为：

1. 先用一个HashMap来记录每个结点的父亲，具体方法为：用key表示当前结点的值，value记录其父节点，这样便于用当前结点的值寻找其父亲；
2. 再维护一个HashSet来记录：p结点寻找父亲直到根结点，所遇到的所有结点值；
3. 用相同的方法，从p结点开始寻找父亲，直到遇到一个2中HashSet中的值，表示找到了最近的公共祖先。

实现代码：

class Solution {
    //维护一个HashMap用于从底向根遍历树
    //key为当前结点值，value为父节点；由key找到value便可以寻找父节点
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    //维护一个HashSet表示哪些结点值访问过（题中说明树中结点值各不相同）
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);//为了建立表示树的HashMap

        //visited表示p到根结点所经过的结点值
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }

        //从q开始也找一遍到根的路，一旦遇到和visited中相同的值，就表示找到了最近共同结点
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}

本题其实用递归法更为简便：

实现代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) {
        	return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //若p和q都没找到，那就没有
        if(left==null&&right==null) {
        	return null;
        }
        if(left==null) {
        	return right;
        }
        if(right==null) {
        	return left;
        }
        return root;
    }
}

复杂度分析：
时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。

空间复杂度：O(N)，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度，因此最后总的空间复杂度为 O(N)。