Medium

题目描述

给定一个整数数组 preorder，它表示一棵二叉搜索树（BST）的先序遍历，请构造这棵树并返回其根节点。

题目保证对于给定的测试用例，总是可以找到满足要求的二叉搜索树。

二叉搜索树是一棵二叉树，对于每个节点，其左子树的所有后代节点的值都严格小于该节点的值，而其右子树的所有后代节点的值都严格大于该节点的值。

二叉树的先序遍历首先显示节点的值，然后遍历 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] <= 1000
  • preorder 的所有值都不同

解题思路

本题有多种解法，都基于BST的性质和先序遍历的特点。

方法一：递归分治（推荐） 利用BST的性质，先序遍历的第一个元素就是根节点。对于根节点，我们需要找到第一个大于根节点值的位置，这个位置之前的所有元素构成左子树，之后的元素构成右子树。递归构造左右子树即可。

方法二：单调栈 使用栈来模拟递归过程。遍历先序数组，对于每个节点：

  • 如果当前值小于栈顶，说明是左子节点
  • 如果当前值大于栈顶，需要弹出栈中所有小于当前值的节点，最后弹出的节点就是当前节点的父节点，当前节点是其右子节点

方法三：边界递归 在递归过程中传递上下界，每次递归时检查当前值是否在合法范围内。

这里采用方法一，因为思路最直观，代码简洁易懂。

代码实现

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return build(preorder, 0, preorder.size() - 1);
    }
    
private:
    TreeNode* build(vector<int>& preorder, int start, int end) {
        if (start > end) return nullptr;
        
        TreeNode* root = new TreeNode(preorder[start]);
        if (start == end) return root;
        
        // 找到第一个大于根节点的位置
        int rightStart = start + 1;
        while (rightStart <= end && preorder[rightStart] < preorder[start]) {
            rightStart++;
        }
        
        // 递归构造左右子树
        root->left = build(preorder, start + 1, rightStart - 1);
        root->right = build(preorder, rightStart, end);
        
        return root;
    }
};

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        def build(start, end):
            if start > end:
                return None
            
            root = TreeNode(preorder[start])
            if start == end:
                return root
            
            # 找到第一个大于根节点的位置
            right_start = start + 1
            while right_start <= end and preorder[right_start] < preorder[start]:
                right_start += 1
            
            # 递归构造左右子树
            root.left = build(start + 1, right_start - 1)
            root.right = build(right_start, end)
            
            return root
        
        return build(0, len(preorder) - 1)

public class Solution {
    public TreeNode BstFromPreorder(int[] preorder) {
        return Build(preorder, 0, preorder.Length - 1);
    }
    
    private TreeNode Build(int[] preorder, int start, int end) {
        if (start > end) return null;
        
        TreeNode root = new TreeNode(preorder[start]);
        if (start == end) return root;
        
        // 找到第一个大于根节点的位置
        int rightStart = start + 1;
        while (rightStart <= end && preorder[rightStart] < preorder[start]) {
            rightStart++;
        }
        
        // 递归构造左右子树
        root.left = Build(preorder, start + 1, rightStart - 1);
        root.right = Build(preorder, rightStart, end);
        
        return root;
    }
}

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var bstFromPreorder = function(preorder) {
    let index = 0;
    
    function build(min, max) {
        if (index >= preorder.length) return null;
        
        let val = preorder[index];
        if (val < min || val > max) return null;
        
        index++;
        let node = new TreeNode(val);
        node.left = build(min, val);
        node.right = build(val, max);
        return node;
    }
    
    return build(-Infinity, Infinity);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 最坏情况下每次都要遍历剩余数组找分割点
空间复杂度O(n) - 递归栈的深度最坏为 n

注意： 可以优化到 O(n) 时间复杂度，使用单调栈或边界递归方法。