★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址： https://www.cnblogs.com/strengthen/p/10504907.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 <= 100The 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 中的值是不同的。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 }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 }
转载于:https://www.cnblogs.com/strengthen/p/10504907.html
