寻找二叉树的最低公共祖先节点

两个节点沿二叉树向上找，找到的第一个公共的节点 

例：D和F之间的最低公共节点：B

       D → B； F → E → B；

       E和G最低公共节点：A

       E → B →  A； G → C →  A；

       B和F最低公共节点：B

       B ； F → E → B；

方法一：

从两个节点开始，生成两条有向无环链表

优化：生成链表主要是为了寻找node1节点的所有父节点，但是对于其中的节点关系没有要求，所以我们可以不使用链表结构，而使用HashSet结构

package binarytree;import java.util.HashMap;
import java.util.HashSet;public class LowestCommonAncester {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public Node lowestCommonAncester(Node head, Node node01, Node node02) {if (head == null) {return null;}HashMap<Node, Node> fatherMap = new HashMap<>();//记录每个节点的父节点，前为子节点，后为父节点fatherMap.put(head, null);//设置头节点的父节点为nullHashSet<Node> set = new HashSet<>();//记录了node01的所有父节点，HashSet集合不保证数据的有序性set.add(node01);//先把node01放进去while (node01 != head) {set.add(fatherMap.get(node01));//把父节点放入set集合中node01 = fatherMap.get(node01);//将node01修改为它的父节点，向上查询}while (node02 != head) {if (set.contains(node02)) {//set集合中存在node02节点向上查询的第一个公共节点即为最低公共节点return node02;}node02 = fatherMap.get(node02);//将node02修改为它的父节点，向上查询}//在node01到头节点的set集合中都没有找到两个节点的公共节点，那么它们一定有个公共节点为头节点return head;}//此方法记录fatherMap集合的数据。即每个节点的父节点public void process(Node node, HashMap<Node, Node> fatherMap) {fatherMap.put(node.left, node);//左孩子的父节点是他自己fatherMap.put(node.right, node);//右孩子的父节点是他自己process(node.left, fatherMap);process(node.right, fatherMap);}
}

方法二：

找到的最低公共节点有三种情况：

        node1是两节点的最低公共节点（node1是node2的其中一个父节点）

        node2是两节点的最低公共节点（node2是node1的其中一个父节点）

        node1和node2无关，两个节点向上查询找到最低公共节点

对于情况一和情况二：当一个节点左右节点一个返回值一个返回空的时候，选择返回值

 

对于情况三：当一个节点左右都不为空的时候，返回它自己

    public Node lowestAncestor(Node node, Node node1, Node node2) {if (node == null || node == node1 || node == node2) {//没有节点或遇到了node1或node2，直接返回当前节点return node;//二叉树最底层的返回，遍历到最底层，或者遇到node1和node2节点}Node left = lowestCommonAncester(node.left, node1, node2);//从左侧返回的node或者nullNode right = lowestCommonAncester(node.right, node1, node2);//从右侧返回的node或者nullif (left != null && right != null) {//当前节点左右返回的值都不为空return node;}return left != null ? left : right;//如果left返回的值为null，就返回右侧right返回的值；如果不是null，返回left的值}