Return the root node of a binary search tree that matches the given preorder
traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left
has a value <
node.val
, and any descendant of node.right
has a value >
node.val
. Also recall that a preorder traversal displays the value of the node
first, then traverses node.left
, then traverses node.right
.)
Example 1:
Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Note:
1 <= preorder.length <= 100
- The values of
preorder
are distinct.
返回与给定先序遍历 preorder
相匹配的二叉搜索树(binary search tree)的根结点。
(回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left
的任何后代,值总 <
node.val
,而 node.right
的任何后代,值总 >
node.val
。此外,先序遍历首先显示节点的值,然后遍历 node.left
,接着遍历 node.right
。)
示例:
输入:[8,5,1,7,10,12] 输出:[8,5,10,1,7,null,12]
提示:
1 <= preorder.length <= 100
- 先序
preorder
中的值是不同的。
Runtime: 12 ms
Memory Usage: 18.8 MB1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func bstFromPreorder(_ preorder: [Int]) -> TreeNode? { 16 var n:Int = preorder.count 17 if n == 0 {return nil} 18 var val:Int = preorder[0] 19 var root:TreeNode? = TreeNode(val) 20 var left:[Int] = [Int]() 21 var right:[Int] = [Int]() 22 for i in 1..<n 23 { 24 if preorder[i] < val 25 { 26 left.append(preorder[i]) 27 } 28 else 29 { 30 right.append(preorder[i]) 31 } 32 } 33 root?.left = bstFromPreorder(left) 34 root?.right = bstFromPreorder(right) 35 return root 36 } 37 }