已知后序序列构建二叉搜索树

思路：

[2,4,3,6,8,7,5]

最后一个是根节点，从后往前找，第一个比根小的数是左子树的根，根前面的数是右子树的根。

就变成了子问题，已知他们的根，怎么构建左子树和右子树

时间复杂度$O(N^2)$

优化用二分法，找比根小的节点，一直找到无法二分。就可以找到有序的部分。遍历行为替换成二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class PosArrayToBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    public static Node posArrayToBST1(int[] posArr) {
        return process1(posArr, 0, posArr.length - 1);
    }

    public static Node process1(int[] posArr, int L, int R) {
        if (L > R) return null;
        Node head = new Node(posArr[R]);
        if (L == R) return head;
        int M = L - 1; // 为了全部是全左或全右子树
        for (int i = L; i < R; i++) {
            if (posArr[i] < posArr[R]) {
                M = i;
            }
        }
        head.left = process1(posArr, L, M);
        head.right = process1(posArr, M + 1, R - 1);
        return head;
    }

    public static Node process2(int[] posArr, int L, int R) {
        Node head = new Node(posArr[R]);
        if (L == R) return head;
        int M = -1;
        for (int i = L; i < R; i++) {
            if (posArr[i] < posArr[R]) {
                M = i;
            }
        }

        if (M == -1) {
            head.right = process1(posArr, L, R - 1);
        } else if (M == R - 1) {
            head.left = process2(posArr, L, R - 1)
        } else {
            head.left = process1(posArr, L, M);
            head.right = process1(posArr, M + 1, R - 1);
        }

        return head;
    }

    public static Node process3(int[] posArr, int L, int R) {
        if (L > R) return null;
        Node head = new Node(posArr[R]);
        if (L == R) return head;
        int M = L - 1;
        int left = L;
        int right = R - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (posArr[mid] < posArr[R]) {
                M = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        head.left = process2(posArr, L, M);
        head.right = process2(posArr, M + 1, R - 1);
        return head;
    }

}