• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1008.先序遍历构造二叉树|ConstructBinarySearchTreefromPreorderTrav ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10504907.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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. 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]

提示:

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

 8ms

 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     var i = 0
16     
17     func bstFromPreorder(_ preorder: [Int]) -> TreeNode? {
18         return bstFromPreorder(preorder, Int.max)
19     }
20     
21     func bstFromPreorder(_ preorder: [Int], _ bound: Int) -> TreeNode? {
22         guard i < preorder.count, preorder[i] < bound else {
23             return nil
24         }
25         
26         var root = TreeNode(preorder[i])
27         i += 1
28         root.left = bstFromPreorder(preorder, root.val)
29         root.right = bstFromPreorder(preorder, bound)
30         return root
31     }
32 }

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 }

12ms

 

 1 class Solution {
 2     func bstFromPreorder(_ preorder: [Int]) -> TreeNode? {
 3         return trialOne(a: preorder)
 4     }
 5     
 6     func trialOne(a: [Int]) -> TreeNode {
 7         guard a.count > 1 else { return TreeNode(a[0]) }
 8         let root = TreeNode(a[0])
 9         let largerIndex = findElementLarger(start: 1, end: a.count-1, a: a) ?? -1
10         if largerIndex != -1 {
11             root.right = trialOne(a: Array(a[largerIndex...a.count-1]))
12         }
13         guard let smallerIndex = findElementSmaller(start: 1, end: a.count-1, a: a) else { return root }
14         if largerIndex != -1 {
15             root.left = trialOne(a: Array(a[smallerIndex...largerIndex-1]))
16         } else {
17             root.left = trialOne(a: Array(a[smallerIndex...a.count-1]))
18         }
19         return root
20     }
21     
22     func findElementLarger(start: Int, end: Int, a: [Int]) -> Int? {
23         guard a.count > 1 else { return nil }
24         for i in start...end {
25             if a[i] > a[0] {
26                 return i
27             }
28         }
29         return nil
30     }
31     
32     func findElementSmaller(start: Int, end: Int, a: [Int]) -> Int? {
33         guard a.count > 1 else { return nil }
34         for i in start...end {
35             if a[i] < a[0] {
36                 return i
37             }
38         }
39         return nil
40     }
41 }

16ms

 1 class Solution {
 2     func bstFromPreorder(_ preorder: [Int]) -> TreeNode? {
 3         return buildTree(0, preorder.count-1, preorder)
 4     }
 5 
 6     func buildTree(_ start: Int, _ end: Int, _ preorder: [Int]) -> TreeNode? {
 7         if start > end { return nil }     
 8         if start == end { return TreeNode(preorder[start]) }
 9         let node = TreeNode(preorder[start])
10         var index = start
11         for i in start+1 ... end {
12             if preorder[i] > node.val {
13                 index = i
14                 break
15             }
16         }
17 
18         if index == start {
19             node.left = buildTree(start+1, end, preorder)
20         }
21         else {
22             node.left = buildTree(start+1, index-1, preorder)
23             node.right = buildTree(index, end, preorder)
24         }
25         return node
26     }
27 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift学习笔记之-自动引用计数发布时间:2022-07-13
下一篇:
swift向方法传数组参数的语法发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap