372，二叉树的最近公共祖先

Believe you can and you're halfway there. 

相信你自己能做到，你就已经成功一半了。

问题描述：

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

例如，给定如下二叉树:  

root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入:

root = [3,5,1,6,2,0,8,null,null,7,4]

p = 5, q = 1

输出: 3

解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入:

root = [3,5,1,6,2,0,8,null,null,7,4]

p = 5, q = 4

输出: 5

解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

问题分析：

要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下

我们看到6和7公共祖先有5和3，但最近的是5。我们只要往上找，找到他们第一个相同的公共祖先节点即可，但怎么找到每个节点的父节点呢，我们只需要把每个节点都遍历一遍，然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径，比如6→5→3，然后在另一个节点往上找，由于7不在那条路径上，我们找7的父节点是2，2也不在那条路径上，我们接着往上找，2的父节点是5，5在那条路径上，所以5就是他们的最近公共子节点。

其实这里我们可以优化一下，我们没必要遍历所有的结点，我们一层一层的遍历（也就是BFS），只需要这两个节点都遍历到就可以了，比如上面2和8的公共结点，我们只需要遍历到第3层，把2和8都遍历到就行了，没必要再遍历第4层了。

我们来看下代码

01非递归写法

 1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 2    //记录遍历到的每个节点的父节点。
 3    Map<TreeNode, TreeNode> parent = new HashMap<>();
 4    Queue<TreeNode> queue = new LinkedList<>();
 5    parent.put(root, null);//根节点没有父节点，所以为空
 6    queue.add(root);
 7    //直到两个节点都找到为止。
 8    while (!parent.containsKey(p) || !parent.containsKey(q)) {
 9        //队列是一边进一边出，这里poll方法是出队，
10        TreeNode node = queue.poll();
11        if (node.left != null) {
12            //左子节点不为空，记录下他的父节点
13            parent.put(node.left, node);
14            //左子节点不为空，把它加入到队列中
15            queue.add(node.left);
16        }
17        //右节点同上
18        if (node.right != null) {
19            parent.put(node.right, node);
20            queue.add(node.right);
21        }
22    }
23    Set<TreeNode> ancestors = new HashSet<>();
24    //记录下p和他的祖先节点，从p节点开始一直到根节点。
25    while (p != null) {
26        ancestors.add(p);
27        p = parent.get(p);
28    }
29    //查看p和他的祖先节点是否包含q节点，如果不包含再看是否包含q的父节点……
30    while (!ancestors.contains(q))
31        q = parent.get(q);
32    return q;
33}

02递归写法

这题我们还可以改一下，使用递归的写法，代码中有注释，就不在详细介绍。

 1public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
 2    if (cur == null || cur == p || cur == q)
 3        return cur;
 4    TreeNode left = lowestCommonAncestor(cur.left, p, q);
 5    TreeNode right = lowestCommonAncestor(cur.right, p, q);
 6    //如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
 7    if (left == null)
 8        return right;
 9    //同上
10    if (right == null)
11        return left;
12    //如果left和right都不为空，说明这两个节点一个在cur的左子树上一个在cur的右子树上，
13    //我们只需要返回cur结点即可。
14    return cur;
15}

03总结

这道题如果一开始就知道每个节点的父节点就更简单了，从每个节点到根节点我们都可以把它看成是一个链表，如果求两个节点的最近公共祖先节点，我们只需要找到这两个链表第一次的交点即可，所以这个时候又是另外一道算法题了。

长按上图，识别图中二维码之后即可关注。

如果喜欢这篇文章就点个"在看"吧