牛客网：在二叉树中找到两个节点的最近公共祖先

原题：

进阶：

再进阶：

我的思路，后序遍历二叉树，找到对应节点，就返回，并且讲函数栈中所有的结点保存为这个节点的所有祖先，第二个结点也是如此。然后以这两个结果的头节点：根节点开始向下遍历，若为最近，则两个结果的下个结点不相等。

如上图，若寻找9和7的最近公共结点，会得到两条链路。

1-3-6-9，1-3-7

然后从1开始寻找，两个链路在3之后的结点不同，则3是最近公共祖先。

书中思路更加简洁：

若找到第一个节点，向上一直返回第一个节点。若找到第二个节点，向上一直返回第二个结点。当对左右子树的函数调用得到的两个结点第一次都不为null，则表明找到了这两个结点，返回这个节点作为最近公共祖先。

import java.util.Scanner;
import java.util.HashMap;

public class Main{
    public static class Node{
        int val;
        Node lch = null;
        Node rch = null;
        public Node(int val){
            this.val = val;
        }
    }
    
    public static void pre_find(Node root){
        if(root != null){
            System.out.print(root.val);
            pre_find(root.lch);
            pre_find(root.rch);
        }
    }
    
    public static Node findAns(Node root,int find1,int find2){
        if(root == null||root.val==find1||root.val==find2){
            return root;
        }
            
        Node left = findAns(root.lch,find1,find2);
        Node right = findAns(root.rch,find1,find2);
        
        if(left!=null&&right!=null){
            return root;
        }
        
        return left == null? right: left;
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String[] f_line_arr = scanner.nextLine().split(" ");
        int num = Integer.parseInt(f_line_arr[0]);
        int root = Integer.parseInt(f_line_arr[1]);
        
        HashMap<Integer,Node> hmap = new HashMap<Integer,Node>();
        
        int temp_root = 0;
        int temp_left = 0;
        int temp_right = 0;
        Node node_root = null;
        Node node_left = null;
        Node node_right = null;
        String[] s_line_arr = null;
        for(int count = 0;count<num;count++){
            s_line_arr = scanner.nextLine().split(" ");
            temp_root = Integer.parseInt(s_line_arr[0]);
            temp_left = Integer.parseInt(s_line_arr[1]);
            temp_right = Integer.parseInt(s_line_arr[2]);
            
            if(hmap.containsKey(temp_root)){
                node_root = hmap.get(temp_root);
            }else{
                node_root = new Node(temp_root);
                hmap.put(temp_root,node_root);
            }
            
            if(temp_left == 0){
                node_left = null;
            }else if(hmap.containsKey(temp_left)){
                node_left = hmap.get(temp_left);
            }else{
                node_left = new Node(temp_left);
                hmap.put(temp_left,node_left);
            }
            
            if(temp_right == 0){
                node_right = null;
            }else if(hmap.containsKey(temp_right)){
                node_right = hmap.get(temp_right);
            }else{
                node_right = new Node(temp_right);
                hmap.put(temp_right,node_right);
            }
            
            node_root.lch = node_left;
            node_root.rch = node_right;
            
                
        }
        String[] t_line_arr = scanner.nextLine().split(" ");
        int find1 = Integer.parseInt(t_line_arr[0]);
        int find2 = Integer.parseInt(t_line_arr[1]);
        
        //pre_find(hmap.get(root));
        System.out.println(findAns(hmap.get(root),find1,find2).val);
    }
}

对于进阶问题，书中思路是建立哈希表，存储自己的父节点，寻找公共祖先，或者是直接建立两个节点的最近公共祖先记录。（若子树头结点为h，h的后代节点和h的最近公共祖先是h，h左子树和右子树的每个节点的最近公共祖先是h，一次遍历迭代得到完整记录，这样每次查询，事件复杂度便是O(1)）