1.给定两个树的节点node1和node2，找到他们最低的公共祖先节点：

方法一：
  1. 遍历整个二叉树，将所有节点的父节点以<Node，Node>形式存入hashmap中
  2. 创建HashSet，从node1开始依据HashMap依次将自己的父节点存入HashSet中
  3. 从node2开始溯洄父节点，一旦存在HashSet中就停止，此时就是首个公共祖先节点
//主函数
public static Node finFather(Node head, Node node1, Node2) {
    HashMap<Node,Node> hashmap = new HashMap<>();
    hashmap.put(head,head);
     process(head,hashmap);
    HashSet<Node> set1 = new HashSet<>();
    
    Node o1 = node1;
    //循环至头节点停下
    while(o1 != hashmap.get(o1)){
        set1.add(o1);
        o1 = hashmap.get(o1);
    }
    //将头节点添加
    set1.add(head);
    
    Node o2 = node2;
    while(set1.get(o2)==null){
        o2 = hashmap.get(o2);
    }
    return o2;
}


//存储父节点函数
public static void process(Node head, HashMap<Node.Node> hashmap) {
    if(hashmap == null) return;
    hashmap.put(head.left,head);
    hashmap.put(head.right,head);
    process(head.left,hashmap);
    process(head.right,hashmap);
}
方法二：

分析node1与node2可能的关系：

  1. node1是node2的祖先 / node2是node1的祖先：返回node1 / node2
  2. node1与node2彼此不互为公共祖先，返回向上汇聚的祖先节点
public static Node findFather(Node head, Node node1, Node node2) {
    if(head == null || head == node1 || head == node2) {
        return head;
    }
    Node left = findFather(head.left, node1, node2);
    Node right = findFather(head.right, node1, node2);
    if(left != null && right != null) {
        return head;
    }
    return left != null ? left : right;
}

2.二叉树找到一个节点的后继节点：

public class Node {
    public Node left;
    public Node right;
    public Node parent;		//指向父节点
    public int value;
    
    public Node(int val) {
        this.value = val;
    }
}

后继节点：中序遍历二叉树后，每个节点的下一个节点是此节点的后继节点

（中序遍历打印每一位节点，相邻的后一个打印的节点是前一位的后继节点，相邻的前一节点是后一节点的前驱节点）

方法一：

中序遍历生成列表，依次查询列表找到后继节点

方法二：

分析后继节点的可能情况：

  1. 当前节点存在右树：后继节点是右树的最左节点
  2. 当前节点没有右树：判断是否为父节点的左孩子：是，父节点为后继；不是，继续看父节点（没有右数说明已经是某左子树最后一个节点）
  3. 前两者无法找到后继节点：后继节点为空，这个节点是二叉树中序遍历的最后一个节点
//主程序
public static Node getNextNode(Node node) {
    if(node == null) return node;
    if(node.right != null) {	//情况1
        return getLeftMost(node);
    }else {
        Node parent = node.parent;
        while(parent != null && parent.left != node) {	//情况2和3
            node = parent;
            parent = node.parent;
        }
        return parent;
    }
}


//走左子树
public static Node getLeftMost(Node node) {
    if(node == null) {
        return node;
    }
    while(node.left != null) {
        node = node.left;
    }
    return node;
}

3.二叉树序列化与反序列化

内存 → 字符串 ：序列化

字符串 → 内存：反序列化

先序序列化：
public static String serialTree(Node head) {
    if(head == null) return "#_";
    String res = head.value + "_";
    res += serialTree(head.left);
    res += serialTree(head.right);
    return res;
}
先序反序列化：
//排序
public static Node reconSerialTree(String str) {
    String[] values = str.split("_");
    Queue<String> queue = new LinkedList<>();
    for(int i = 0; i != values.length; i++) {
        queue.add(values[i]);
    }
    return reconOrder(queue);
}

//组成树
public static Node reconOrder(Queue<String> queue) {
    String value = queue.poll();
    if(value.equals("#")){
        return null;
    }
    Node head = new Node(Integer.valueOf(value));
    head.left = reconOrder(queue);
    head.right = reconOrder(queue);
    return head;
}
中序，后序同理