construct-binary-search-tree-from-preorder-traversal

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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 <code>Node.left</code> has a value strictly less than <code>Node.val</code>, and any descendant of <code>Node.right</code> has a value strictly greater than <code>Node.val</code>.

A preorder traversal of a binary tree displays the value of the node first, then traverses <code>Node.left</code>, then traverses <code>Node.right</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2019/03/06/1266.png" style="height: 386px; width: 590px;" />
<pre>
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
</pre>

Example 2:

<pre>
Input: preorder = [1,3]
Output: [1,null,3]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 100</code></li>
	<li><code>1 &lt;= preorder[i] &lt;= 1000</code></li>
	<li>All the values of <code>preorder</code> are unique.</li>
</ul>

第 127 场周赛

weekly-contest-127

bstFromPreorder

高级专家

Construct Binary Search Tree from Preorder Traversal

Stack

Tree

Binary Search Tree

Array

Binary Tree

Monotonic Stack

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

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

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

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

&nbsp;

示例 1：

<img src="https://assets.leetcode.com/uploads/2019/03/06/1266.png" />

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

示例 2:

<pre>
输入: preorder = [1,3]
输出: [1,null,3]
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 100</code></li>
	<li><code>1 &lt;= preorder[i]&nbsp;&lt;= 10^8</code></li>
	<li><code>preorder</code> 中的值 互不相同</li>
</ul>

&nbsp;