每日算法之在二叉树中找到两个节点的最近公共祖先

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

题目

1. 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
3. 注：本题保证二叉树中每个节点的val值均不相同。

复制代码

方法 BFS，非递归方法

思路

算法实现

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

复制代码

代码

1. package mid.JZ86在二叉树中找到两个节点的最近公共祖先;
3. import java.util.*;
5. class TreeNode {
6.     int val = 0;
7.     TreeNode left = null;
8.     TreeNode right = null;
9. }
11. public class Solution {
12.     /**
13.      * @param root TreeNode类
14.      * @param o1   int整型
15.      * @param o2   int整型
16.      * @return int整型
17.      */
18.     public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
19.         // write code here
20.         Queue<TreeNode> queue = new LinkedList<>();
21.         //记录父节点
22.         Map<Integer, Integer> parent = new HashMap<>();
23.         parent.put(root.val, Integer.MIN_VALUE);
24.         queue.add(root);
25.         //BFS
26.         while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
27.             TreeNode node = queue.poll();
28.             //左子树
29.             if (node.left != null) {
30.                 //记录父亲节点
31.                 parent.put(node.left.val, node.val);
32.                 queue.add(node.left);
33.             }
34.             //左子树
35.             if (node.right != null) {
36.                 //记录父亲节点
37.                 parent.put(node.right.val, node.val);
38.                 queue.add(node.right);
39.             }
40.         }
42.         //记录祖先节点
43.         Set<Integer> ancestors = new HashSet<>();
44.         //列出o1的所有祖先节点
45.         while (parent.containsKey(o1)) {
46.             ancestors.add(o1);
47.             o1 = parent.get(o1);
48.         }
50.         while(!ancestors.contains(o2)) {
51.             o2 = parent.get(o2);
52.         }
53.         return o2;
54.     }
55. }

复制代码