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

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

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>

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;