177 在二叉树中找到两个节点的最近公共祖先
Table of Contents

ac

补充：倍增LCA算法（大跳算法）

获取到两个节点到路径，然后求公共部分，需要额外空间O(h)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long) Math.pow(2, 29);

    public static void main(String[] args) throws Exception {
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int val = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);

            if (!mp.containsKey(val)) {
                mp.put(val, new TreeNode(val));
            }
            if (leftVal != 0) {
                if (!mp.containsKey(leftVal)) {
                    mp.put(leftVal, new TreeNode(leftVal));
                }
                mp.get(val).left = mp.get(leftVal);
            }
            if (rightVal != 0) {
                if (!mp.containsKey(rightVal)) {
                    mp.put(rightVal, new TreeNode(rightVal));
                }
                mp.get(val).right = mp.get(rightVal);
            }
        }
        line = reader.readLine();
        strArr = line.split(" ");
        int p = Integer.valueOf(strArr[0]);
        int q = Integer.valueOf(strArr[1]);
        TreeNode root = mp.get(rootVal);
        System.out.println(findNode(root, p, q));
    }

    //
    static int findNode(TreeNode root, int p, int q){
        List<Integer> path = new ArrayList<>();
        dfs(root,path, p, q);
        int ans = firstSame(path1, path2);
        return ans;
    }

    static int firstSame( List<Integer> l1,  List<Integer> l2){
        int size1 = l1.size();
        int size2 = l2.size();
        int i = 0;
        int j = 0;
        while (i < size1 && j < size2 && l1.get(i).equals(l2.get(j))){
            i ++;
            j ++;
        }
        return l1.get(i - 1);
    }

    static void dfs(TreeNode root, List<Integer> path, int p, int q){
        if(root == null){
            return;
        }
        if(root.val == p){
           for(Integer i: path){
               path1.add(i);
           }
           path1.add(p);
        }
        if(root.val == q){
            for(Integer i: path){
                path2.add(i);
            }
            path2.add(q);
        }
        path.add(root.val);
        int size = path.size();
        dfs(root.left, path, p ,q);
        dfs(root.right, path, p ,q);
        path.remove(size-1);
    }

    static List<Integer> path1 = new ArrayList<>();
    static List<Integer> path2 = new ArrayList<>();
}
/*
         6
      /     \
     3       9
    / \      / \
   1  4     8  10
    \  \   /
     2  5 7

10 6
6 3 9
3 1 4
1 0 2
2 0 0
4 0 5
5 0 0
9 8 10
10 0 0
8 7 0
7 0 0
7 5

3

8 1
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0
7 8 0
8 0 0
4 5

2
 */

直接后序遍历递归法

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long) Math.pow(2, 29);

    public static void main(String[] args) throws Exception {
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int val = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);

            if (!mp.containsKey(val)) {
                mp.put(val, new TreeNode(val));
            }
            if (leftVal != 0) {
                if (!mp.containsKey(leftVal)) {
                    mp.put(leftVal, new TreeNode(leftVal));
                }
                mp.get(val).left = mp.get(leftVal);
            }
            if (rightVal != 0) {
                if (!mp.containsKey(rightVal)) {
                    mp.put(rightVal, new TreeNode(rightVal));
                }
                mp.get(val).right = mp.get(rightVal);
            }
        }
        line = reader.readLine();
        strArr = line.split(" ");
        int p = Integer.valueOf(strArr[0]);
        int q = Integer.valueOf(strArr[1]);
        TreeNode ancestor = findAncestorNode(mp.get(rootVal), mp.get(p), mp.get(q));
        System.out.println(ancestor == null? 0 : ancestor.val);
    }

    //
    static TreeNode findAncestorNode(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }
        if(root.val == p.val || root.val == q.val){
            return root;
        }
        TreeNode ancestor1 = findAncestorNode(root.left, p, q);
        TreeNode ancestor2 = findAncestorNode(root.right, p, q);
        // 要么是root， 要么是root左边的某个节点，要么是右边的节点
        if(ancestor1 == null && ancestor2 != null){
            return ancestor2;
        }
        if(ancestor1 != null && ancestor2 == null){
            return ancestor1;
        }
        if(ancestor1 != null && ancestor2 != null && ancestor1 == ancestor2){
            return ancestor1;
        }
        if(ancestor1 == null && ancestor2 == null){
            return null;
        }
        return root;
    }

}
/*
         6
      /     \
     3       9
    / \      / \
   1  4     8  10
    \  \   /
     2  5 7

10 6
6 3 9
3 1 4
1 0 2
2 0 0
4 0 5
5 0 0
9 8 10
10 0 0
8 7 0
7 0 0
4 5

4

         1
      /     \
     2       3
    / \      / \
   4  5     6  7
              /
             8

8 1
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0
7 8 0
8 0 0
4 5

2
 */