二叉树：给定一棵二叉树的头节点head，和另外两个节点a和b，返回a和b的最低公共祖先-年长大叔的用心爱爱漫画
@[toc]
# 1. 题目描述
给定一棵二叉树的头节点head，和另外两个节点a和b，返回a和b的最低公共祖先。
# 2. 测试案例
* 树空
* 树不空
# 3. 最佳思路
## 3.1 笔试
```
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
Node node = right(null, root, root.right.left);
System.out.println(node == null ? node : node.value);
}
// 找到a和b的最小公共祖先
public static Node right(Node root, Node a, Node b) {
/* 0. 边界条件 */
if (root == null)
return null;
/* 1. key=当前结点，value=当前结点的父结点。遍历二叉树，放入map中 */
Map<Node, Node> map = new HashMap<>();
fillMap(root, map);
map.put(root, null); // 根结点没有父结点，记得为根结点添加null父结点
/* 2. 将a的祖先结点放入一个set中*/
Set set = new HashSet<>();
Node parent = map.get(a);
while (parent != null) {
set.add(parent);
parent = map.get(parent);
}
/* 3. 依次找b的祖先结点，并判断此结点是否在set中。若在，则找到最小公共祖先，若不在则不存在最小公共祖先 */
parent = map.get(b);
while (parent != null) {
if (set.contains(parent))
return parent;
parent = map.get(parent);
}
return null;
}
public static void fillMap(Node cur, Map<Node, Node> map) {
if (cur.left != null) {
map.put(cur.left, cur);
fillMap(cur.left, map);
}
if (cur.right != null) {
map.put(cur.right, cur);
fillMap(cur.right, map);
}
}
}
```
## 3.2 面试
假设当前结点为x结点。那么当x的左孩子包含a，右孩子包含b；或x的左孩子包含b，右孩子包含a时。此时的x结点就是最小祖先结点。只需要记录下来即可。
由于是采用二叉树的后序遍历解题，传参数并不能解决问题。有2个解决方法：
1. 设置一个全局变量用于保存结果。
2. 在Info类中添加一个字段用于保存信息。
选第二种较好，最终Info类有3个字段。
> 代码说明：
> 
```
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
static class Info {
public boolean isContainA; // 是否包含a
public boolean isContainB; // 是否包含b
public Node minParent; // 最小公共祖先
public Info(boolean isContainA, boolean isContainB, Node minParent) {
this.isContainA = isContainA;
this.isContainB = isContainB;
this.minParent = minParent;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
Node node = findMinParent(null, root.left.left, root.right.left);
System.out.println(node == null ? node : node.value);
}
// 找到a和b的最小公共祖先
public static Node findMinParent(Node root, Node a, Node b) {
return pos(root, a, b).minParent;
}
// 利用二叉树的后序遍历解题
public static Info pos(Node cur, Node a, Node b) {
/* 0.边界条件 */
if (cur == null)
return new Info(false, false, null);
/* 1. 获取左右孩子的信息 */
Info leftInfo = pos(cur.left, a, b);
Info rightInfo = pos(cur.right, a, b);
/* 2. 实例化当前结点的info对象，将其属性设置正确，最后返回 */
// (1) 实例化info对象
Info info = new Info(false, false, null);
// (2) 设置info的isContainA与isContainB属性值
info.isContainA = leftInfo.isContainA || rightInfo.isContainA;
info.isContainB = leftInfo.isContainB || rightInfo.isContainB;
// (3) 设置info的minParent属性值
if (info.isContainA && info.isContainB)
info.minParent = cur;
info.isContainA = info.isContainA || cur == a;
info.isContainB = info.isContainB || cur == b;
// 保证后序结点能够正确保存结果
if (leftInfo.minParent != null)
info.minParent = leftInfo.minParent;
if (rightInfo.minParent != null)
info.minParent = rightInfo.minParent;
// (4) 返回info对象
return info;
}
}
```
# 4. 代码
```
import java.util.*;
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
static class Info {
public boolean isContainA; // 是否包含a
public boolean isContainB; // 是否包含b
public Node minParent; // 最小公共祖先
public Info(boolean isContainA, boolean isContainB, Node minParent) {
this.isContainA = isContainA;
this.isContainB = isContainB;
this.minParent = minParent;
}
}
public static void main(String[] args) {
int testCount = 1000000; //测试次数
int maxHeight = 100; // 创建的最大树高
int maxValue = 100; // 树结点的最大值
boolean isSucceed = true;
for (int i = 0; i < testCount; i++) {
// 随机创建一颗二叉树
Node root = randomCreatBT(maxHeight, maxValue);
// 随机找到二叉树的两个最底部的结点
Node a = randomFindBTNode(root);
if (a == null) // 若a == null，说明root == null或只有一个结点，那么a，b无最小公共结点
continue; // 且更加重要的是会导致下面第二行while陷入死循环，故要使用continue跳过
Node b = null;
while ((b = randomFindBTNode(root)) == a) ; // 保证a与b不是同一个结点
// 使用两种方式分别获取结果，并比较是否相同
Node ans1 = right(root, a, b);
Node ans2 = findMinParent(root, a, b);
if (ans1 != ans2) {
printBT(root, 0, 20, "根:");
System.out.println("结点a:" + a.hashCode() + " " + a.value);
System.out.println("结点b:" + b.hashCode() + " " + b.value);
System.out.println("right:" + (ans1 == null ? "null" : (ans1.hashCode() + " " + ans1.value)));
System.out.println("findMinParent:" + (ans2 == null ? "null" : (ans2.hashCode() + " " + ans2.value)));
isSucceed = false;
break;
}
}
System.out.println(isSucceed ? "nice!" : "fuck!");
}
// 随机创建一个二叉树
public static Node randomCreatBT(int maxHeight, int maxValue) {
return creatNode(maxHeight, maxValue, 1); // 确定了要生成的树高
}
public static Node creatNode(int maxHeight, int maxValue, int curHeight) {
Node cur = null;
if (Math.random() > 0.5 && curHeight <= maxHeight) {
cur = new Node((int) (Math.random() * (maxValue + 1)));
cur.left = creatNode(maxHeight, maxValue, curHeight + 1);
cur.right = creatNode(maxHeight, maxValue, curHeight + 1);
}
return cur;
}
// 打印一颗二叉树
public static void printBT(Node cur, int height, int len, String flag) {
if (cur == null)
return;
// 右
printBT(cur.right, height + 1, len, "R:");
// 根
printNode(cur, height, len, flag);
// 左
printBT(cur.left, height + 1, len, "L:");
}
public static void printNode(Node cur, int height, int len, String flag) {
StringBuffer str = new StringBuffer(len * (height + 1));
// 前空格
for (int i = 0; i < height * len; i++)
str.append(" ");
String valueStr = flag + cur.hashCode() + " " + cur.value;
int leftSpaces = len - valueStr.length() >> 1;
int rightSpaces = len - leftSpaces - valueStr.length();
// 左空格
for (int i = 0; i < leftSpaces; i++)
str.append(" ");
// 值
str.append(valueStr);
// 右空格
for (int i = 0; i < rightSpaces; i++)
str.append(" ");
System.out.println(str);
}
// 随机找到二叉树的某个结点
public static Node randomFindBTNode(Node root) {
/* 0. 边界条件 */
if (root == null || (root.left == null && root.right == null))
return null;
/* 1. 采用某种方式遍历树，并将结果放入list中。(这里采用先序遍历) */
List<Node> list = new LinkedList<>();
pre(root, list);
/* 2. 从list中随机选出一个下标，并返回该下标所在结点 */
return list.get((int) (Math.random() * list.size()));
}
public static void pre(Node cur, List<Node> list) {
if (cur == null)
return;
list.add(cur);
pre(cur.left, list);
pre(cur.right, list);
}
// 找到a和b的最小公共祖先
public static Node findMinParent(Node root, Node a, Node b) {
return pos(root, a, b).minParent;
}
// 利用二叉树的后序遍历解题
public static Info pos(Node cur, Node a, Node b) {
/* 0.边界条件 */
if (cur == null)
return new Info(false, false, null);
/* 1. 获取左右孩子的信息 */
Info leftInfo = pos(cur.left, a, b);
Info rightInfo = pos(cur.right, a, b);
/* 2. 实例化当前结点的info对象，将其属性设置正确，最后返回 */
// (1) 实例化info对象
Info info = new Info(false, false, null);
// (2) 设置info的isContainA与isContainB属性值
info.isContainA = leftInfo.isContainA || rightInfo.isContainA;
info.isContainB = leftInfo.isContainB || rightInfo.isContainB;
// (3) 设置info的minParent属性值
if (info.isContainA && info.isContainB)
info.minParent = cur;
info.isContainA = info.isContainA || cur == a;
info.isContainB = info.isContainB || cur == b;
// 保证后序结点能够正确保存结果
if (leftInfo.minParent != null)
info.minParent = leftInfo.minParent;
if (rightInfo.minParent != null)
info.minParent = rightInfo.minParent;
// (4) 返回info对象
return info;
}
// 找到a和b的最小公共祖先
public static Node right(Node root, Node a, Node b) {
/* 0. 边界条件 */
if (root == null)
return null;
/* 1. key=当前结点，value=当前结点的父结点。遍历二叉树，放入map中 */
Map<Node, Node> map = new HashMap<>();
fillMap(root, map);
map.put(root, null); // 根结点没有父结点，记得为根结点添加null父结点
/* 2. 将a的祖先结点放入一个set中*/
Set set = new HashSet<>();
Node parent = map.get(a);
while (parent != null) {
set.add(parent);
parent = map.get(parent);
}
/* 3. 依次找b的祖先结点，并判断此结点是否在set中。若在，则找到最小公共祖先，若不在则不存在最小公共祖先 */
parent = map.get(b);
while (parent != null) {
if (set.contains(parent))
return parent;
parent = map.get(parent);
}
return null;
}
public static void fillMap(Node cur, Map<Node, Node> map) {
if (cur.left != null) {
map.put(cur.left, cur);
fillMap(cur.left, map);
}
if (cur.right != null) {
map.put(cur.right, cur);
fillMap(cur.right, map);
}
}
}
```