1008. Construct Binary Search Tree from Preorder Traversal
1008. Construct Binary Search Tree from Preorder Traversal
🟠 🔖 栈
树
二叉搜索树
数组
二叉树
单调栈
🔗 LeetCode
题目
Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree ), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left
has a value strictly less than Node.val
, and any descendant of Node.right
has a value strictly greater than Node.val
.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left
, then traverses Node.right
.
Example 1:
![](https://assets.leetcode.com/uploads/2019/03/06/1266.png)
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3]
Output: [1,null,3]
Constraints:
1 <= preorder.length <= 100
1 <= preorder[i] <= 1000
- All the values of
preorder
are unique.
题目大意
给定一个整数数组,它表示 BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。
保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树,其中每个节点, Node.left
的任何后代的值 严格小于 Node.val
, Node.right
的任何后代的值 严格大于 Node.val
。
二叉树的 前序遍历 首先显示节点的值,然后遍历Node.left
,最后遍历Node.right
。
解题思路
构造二叉树,先找到根节点,再递归地构造左右子树。
本题中已知二叉搜索树的先序遍历,根节点就是数组的第一个元素。
只需要再找出左右子树分割的地方,就可以递归构造左右子树了。根据二叉搜索树的特点,左子树的所有值都小于根节点,所以只需遍历后续数组,找到第一个比根节点大的数值,即为右子树先序遍历的第一个元素。
代码
/**
* @param {number[]} preorder
* @return {TreeNode}
*/
var bstFromPreorder = function (preorder) {
if (!preorder.length) return null;
let root = new TreeNode(preorder[0]);
let mid = 1;
while (preorder[mid] < preorder[0]) {
mid++;
}
root.left = bstFromPreorder(preorder.slice(1, mid));
root.right = bstFromPreorder(preorder.slice(mid));
return root;
};