【树】B039

    技术2022-07-13  69

    一、Problem

    Return the root node of a binary search tree that matches the given preorder traversal.

    Constraints:

    1 <= preorder.length <= 100 1 <= preorder[i] <= 10^8 The values of preorder are distinct.

    二、Solution

    方法一:递归

    思路

    根据 BST 性质可得,a[0] 就是 BST 的根,从左往右数第一个大于 a[0] 的值就是右子树的开端,可基于这一点递归构造左右子树

    class Solution { TreeNode dfs(int l, int r, int[] a) { if (l > r) return null; TreeNode root = new TreeNode(a[l]); int rStart = l; while (rStart <= r && a[rStart] <= a[l]) rStart++; root.left = dfs(l+1, rStart-1, a); root.right = dfs(rStart, r, a); return root; } public TreeNode bstFromPreorder(int[] preorder) { return dfs(0, preorder.length-1, preorder); } }
    复杂度分析
    时间复杂度: O ( n ) O(n) O(n),空间复杂度: O ( 1 ) O(1) O(1)
    Processed: 0.028, SQL: 9