给定一棵二叉树的头节点head,和另外两个节点a和b。返回a和b的最低公共祖先（a和b有可能不在这棵树上）
最低公共祖先：a和b往上走初次交汇的点
方法一
不用二叉树的递归套路：准备一张HashMap和HashSet，在遍历整棵树的时候，HashMap用来存放每个结点和父结点。a结点一直往父结点方向走，沿途全部加入HashSet，然后b结点往上走的过程，第一个在HashSet里的就是两个结点的最低公共祖先。 这个方法缺点很明显，虽然时间复杂度仍然是O(N)，但是不够简洁。不仅跑了个递归，而且还填满了一张表，之后还要从指定结点往上回溯，沿途结点加入HashSet，然后用另外一个结点来回溯比较。太麻烦啦！！！
方法二
二叉树的递归套路：按照惯例，我们来列可能性（假设以X为头节点的整棵树）
1）a和b都不在以X为头结点的整棵树上
2）a和b只有一个在以X为头结点的整棵树上
3）a和b都在以x为头结点的树上（又有四种情况）
1》左树右树各一个
2》左树有两个
3》右树有两个
4》x自己是a或b
整合一下，任何子树需要返回信息就是：
public static class Info{ // a和b最初交汇点，没有交汇点返回null public Node ans; // 在子树上是否发现a public boolean findA; // 在子树上是否发现b public boolean findB; public Info(Node n,boolean fa,boolean fb) { ans=n; findA=fa; findB=fb; } }
完整代码：
package com.harrison.class08; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; public class Code09_LowestAncestor { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static Node lowestAncestor1(Node head, Node a, Node b) { if (head == null) { return null; } HashMap<Node, Node> parentMap = new HashMap<>(); parentMap.put(head, null); fillParentMap(head, parentMap); HashSet<Node> aSet = new HashSet<>(); Node cur = a; aSet.add(cur); while (parentMap.get(cur) != null) { cur = parentMap.get(cur); aSet.add(cur); } cur = b; while (!aSet.contains(cur)) { cur = parentMap.get(cur); } return cur; } public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) { if (head.left != null) { parentMap.put(head.left, head); fillParentMap(head.left, parentMap); } if (head.right != null) { parentMap.put(head.right, head); fillParentMap(head.right, parentMap); } } public static class Info { // a和b最初交汇点，没有交汇点返回null public Node ans; // 在子树上是否发现a public boolean findA; // 在子树上是否发现b public boolean findB; public Info(Node n, boolean fa, boolean fb) { ans = n; findA = fa; findB = fb; } } public static Info process1(Node head, Node a, Node b) { if (head == null) { return new Info(null, false, false); } Info leftInfo = process1(head.left, a, b); Info rightInfo = process1(head.right, a, b); // 如何算是发现这个结点，要么头节点是，要么左树上有，要么右树上有 boolean findA = (head == a || leftInfo.findA || rightInfo.findA); boolean findB = (head == b || leftInfo.findB || rightInfo.findB); // 先假设a,b没有交汇点 // a和b的交汇点在哪？ // 左树上提前交会 || 右树上提前交会 || 两边都没有提前交会，那就是头节点处交会 Node ans = null; if (leftInfo.ans != null) { ans = leftInfo.ans; } if (rightInfo.ans != null) { ans = rightInfo.ans; } if (ans == null) { if (findA && findB) { ans = head; } } return new Info(ans, findA, findB); } public static Node lowestAncestor2(Node head, Node a, Node b) { return process1(head, a, b).ans; } public static Node generateRandomBST(int maxLevel, int maxValue) { return generate(1, maxLevel, maxValue); } public static Node generate(int level, int maxLevel, int maxValue) { if (level > maxLevel || Math.random() < 0.5) { return null; } Node head = new Node((int) (Math.random() * maxValue)); head.left = generate(level + 1, maxLevel, maxValue); head.right = generate(level + 1, maxLevel, maxValue); return head; } public static Node pickRandomOne(Node head) { if (head == null) { return null; } ArrayList<Node> arr = new ArrayList<>(); fillPreList(head, arr); int randomIndex = (int) (Math.random() * arr.size()); return arr.get(randomIndex); } public static void fillPreList(Node head, ArrayList<Node> arr) { if (head == null) { return; } arr.add(head); fillPreList(head.left, arr); fillPreList(head.right, arr); } public static void main(String[] args) { int maxLevel = 4; int maxValue = 100; int testTimes = 1000000; for (int i = 0; i < testTimes; i++) { Node head = generateRandomBST(maxLevel, maxValue); Node o1 = pickRandomOne(head); Node o2 = pickRandomOne(head); if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) { System.out.println("Oops!"); } } System.out.println("finish!"); } }
