1008. Construct Binary Search Tree from Preorder Traversal¶
题目信息¶
- 题号:
1008
- 难度:
Medium
- 主题:
二叉搜索树、先序遍历、树构造
- 原题:
- 重点:
preorder是一棵节点值互不相同的二叉搜索树的先序遍历;需恢复满足左小右大的原树结构
题目重述¶
给定整数数组 preorder,它是一棵二叉搜索树按“根节点、左子树、右子树”顺序得到的先序遍历结果。数组中的节点值互不相同。
请构造并返回这棵二叉搜索树的根节点。对树中每个节点,左子树所有值都严格小于节点值,右子树所有值都严格大于节点值;题目保证输入对应的结果唯一。
1 <= preorder.length <= 100,1 <= preorder[i] <= 1000,所有元素互不相同。
自建示例¶
左右子树都包含多层节点:
输入:preorder = [7,3,1,5,10,9]
输出:[7,3,10,1,5,9]
解释:根节点为 7;3、1、5 构成左子树,10、9 构成右子树。该树的先序遍历恰好为给定数组。
只有一个节点:
输入:preorder = [6]
输出:[6]
解释:唯一元素直接成为根节点,左右子树均为空。