[Swift Weekly Contest 127]LeetCode1008. 先序遍历构造二叉树 | Construct Binary Search Tree from Preorder Trave

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]
[Swift Weekly Contest 127]LeetCode1008. 先序遍历构造二叉树 | Construct Binary Search Tree from Preorder Trave

Note: 

  1. 1 <= preorder.length <= 100
  2. 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]
[Swift Weekly Contest 127]LeetCode1008. 先序遍历构造二叉树 | Construct Binary Search Tree from Preorder Trave

[Swift Weekly Contest 127]LeetCode1008. 先序遍历构造二叉树 | Construct Binary Search Tree from Preorder Trave

提示:

  1. 1 <= preorder.length <= 100
  2. 先序 preorder 中的值是不同的。

 Runtime: 12 ms

Memory Usage: 18.8 MB
 1 /**
 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 }

 

上一篇:AcWing 18. 重建二叉树(前序+中序)


下一篇:[Lintcode]66. Binary Tree Preorder Traversal/[Leetcode]144. Binary Tree Preorder Traversal