1008. 前序遍历构造二叉搜索树 - 力扣（LeetCode）

一、题目

给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12] 

示例 2：
输入: preorder = [1,3]
输出: [1,null,3]

提示：

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• preorder 中的值 互不相同

二、代码

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        // 过滤无效参数
        if (preorder == null || preorder.length == 0) {
            return null;
        }

        int n = preorder.length;
        // 记录先序序列中每一个位置右遍最近的比他的的数的位置
        // nearBig[i] = x 表示先序序列i位置中，右遍离它最近的大于大的数的位置为x
        int[] nearBig = new int[n];
        // 先初始化成-1，表示右边没有比自己大的数了
        for (int i = 0; i < n; i++) {
            nearBig[i] = -1;
        }

        // 使用单调栈，找到每一个位置右遍里它最近的并且大于它的数
        // 栈中的数据自底向上，从大到小
        int[] stack = new int[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            // 把需要弹出的数据都从栈中弹出来，并记录弹出位置的右边最近比它大的数的位置
            while (top != -1 && preorder[i] >  preorder[stack[top]]) {
                nearBig[stack[top]] = i;
                top--;
            } 

            stack[++top] = i;
        }

        // 递归构造二叉树
        return process(preorder, 0, n - 1, nearBig);
    }

    // 返回先序序列中l~r范围上的节点构成的二叉树的头节点
    public TreeNode process(int[] preorder, int l, int r, int[] nearBig) {
        // 表示此时已经遍历到不合法位置了，说明此时这个应该是到了最底部的空节点，返回null
        if (l > r) {
            return null;
        }

        // 在先序序列中任意范围上的数，最左边的一定是这些数组成的二叉树的头节点
        // 找到此时l位置作为头节点，它右遍最近的比他大的位置，找到的这个位置及其右边的所有数，就构成了l为头节点的二叉搜索树的右子树
        // 如果此时l右边已经没有比他大的数了，或者比他大的数就不在当前这个树的l~r的范围上，就说明当前l为头节点的这棵树就没有右子树，设置为r+1，在下一层递归的就返回null
        int next = (nearBig[l] == -1 || nearBig[l] > r) ? r + 1 : nearBig[l];
        
        // 向下递归构造左子树  l + 1 ~ next-1就是l为根节点的左子树的所有节点
        TreeNode left = process(preorder, l + 1, next - 1, nearBig);
        // 向下递归构造右子树  next ~ r就是l为根节点的右子树的所有节点
        TreeNode right = process(preorder, next, r, nearBig);

        // 构造二叉树根节点
        TreeNode head = new TreeNode(preorder[l], left, right);
        // 返回当前这棵树的根节点
        return head;
    }
}

三、解题思路 

要了解先序序列的特点，在先序序列中任意范围上的数，最左边的一定是这些数组成的二叉树的头节点，这个头结点的左右子孩子就在先序序列中头节点的右边。我们要利用这个特点，来递归寻找到每一个头结点的左右子树的范围。这个题给的是搜索二叉树，所以每个结点的大小都是有序的。也就是说搜索二叉树先序序列中，头节点右边的节点中，第一个大于头节点的位置以及它右边的所有数，就是该头节点的右子树中的所有节点，剩下的就是头节点左子树中的所有节点。