经典面试题(二)--二叉树的最近公共祖先
来源：LeetCode
难度：简单
描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例1：
示例2：
分析：题意还是比较明确的，给咱们一颗二叉树和两个节点值，让找出这两个节点值的最近公共祖先，这里咱们可以遍历每个节点值，看该节点是不是p和q的祖先，找到所有符合条件中深度最深的那个就是咱们要找的解；咱们也可以把每个节点的父节点记录下来，这样从下往上找也可解题，具体解法如下
题外话：二叉树结构和链表类似，只有往下的指针且无法直接定位某个节点，所以如果面试时咱们一时没有好的思路，可以遍历二叉树，将每个节点的父节点保存起来，这样咱们可以直接定位节点及其上下节点，能更好的解题
解题
方法一：暴力递归法
思路：如分析，用递归法遍历左右子树查询是否存在p、q节点，这里有以下几种情况：
左右子树没有p、q节点，则表明当前树不存在p、q公共祖先
有一个子树未查到任意节点，那么最近公共祖先在另一颗子树当中
两个子树都查到了任意节点，那么当前节点就是最近公共祖先
代码：
1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2 //如果 当前根为null，或者 当前根为任意目标节点 返回root
3 if (root == null || root == p || root == q) {
4 return root;
5 }
6
7 //分别向 左子树 和 右子树 查询两个目标节点是否存在
8 TreeNode leftRoot = lowestCommonAncestor(root.left, p, q);
9 TreeNode rightRoot = lowestCommonAncestor(root.right, p, q);
10 //若 都没有查到，则表示当前树中，不存在目标节点
11 if (leftRoot == null && rightRoot == null) {
12 return null;
13 }
14 //若 其中一棵子树没有查到，则公共祖先为 另一棵子树
15 if (leftRoot == null) {
16 return rightRoot;
17 }
18 if (rightRoot == null) {
19 return leftRoot;
20 }
21 //若 都查询到了，则目标节点在当前root两侧，
22 //即：当前root为 最近公共祖先
23 return root;
24}
时间复杂度：O(n)
空间复杂度：O(n)
方法二：Map缓存法
思路：如分析，咱们用map存储每个节点对应的父节点，然后从p、q中任意选一个节点一直往上找，并进行标识，知道root节点，然后再从p、q中另一个节点往上找，当找到第一个已经被标识的节点时，该节点就是最近的公共祖先节点
代码：
1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2 if (root == null) {
3 return null;
4 }
5 Map<TreeNode, TreeNode> node2Father = new HashMap<>();
6 buildNode2Father(root, node2Father);
7 //用于标识已经被遍历过的父节点
8 Set<Integer> set = new HashSet<>();
9 while (p != null) {
10 //将遍历过的节点进行标识
11 set.add(p.val);
12 //往上找父节点
13 p = node2Father.get(p);
14 }
15 while (q != null) {
16 //如果找到的节点已经被标识，那么该节点就是p、q的最近公共祖先
17 if (set.contains(q.val)) {
18 return q;
19 }
20 //将遍历过的节点进行标识
21 set.add(q.val);
22 //往上找父节点
23 q = node2Father.get(q);
24 }
25 //树中不存在p、q公共祖先
26 return null;
27}
28
29private void buildNode2Father(TreeNode root, Map<TreeNode, TreeNode> node2Father) {
30 if (root == null) {
31 return;
32 }
33 //root节点就是父节点，将其左右子节点指向它即可
34 if (root.left != null) {
35 node2Father.put(root.left, root);
36 //处理左子树为父节点的情况
37 buildNode2Father(root.left, node2Father);
38 }
39 if (root.right != null) {
40 node2Father.put(root.right, root);
41 //处理右子树为父节点的情况
42 buildNode2Father(root.right, node2Father);
43 }
44}
时间复杂度：O(n)
空间复杂度：O(n)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐