[Swift]LeetCode105.从前序与中序遍历序列构造二叉树|ConstructBinaryTreefromPreorde ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

[Swift]LeetCode105.从前序与中序遍历序列构造二叉树|ConstructBinaryTreefromPreorde ...

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

32ms

 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 
15 extension Array {
16     subscript(safe index: Int) -> Element? {
17         guard index >= 0 && index < self.count else {
18             return nil
19         }
20 
21         return self[index]
22     }
23 }
24 
25 class Solution {
26     func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
27         guard let rootValue = preorder[safe: 0] else {
28             return nil
29         }
30 
31         var inorderMap: [Int: Int] = [:]
32         for index in 0..<inorder.count {
33             inorderMap[inorder[index]] = index
34         }
35         let root = TreeNode(rootValue)
36 
37         buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: 0, root: root, tooFarValue: nil)
38 
39         return root
40     }
41 
42     func buildNextNode(inorder: [Int], preorder: [Int], inorderMap: [Int: Int], currentPreOrderIndex: Int, root: TreeNode, tooFarValue: Int?) -> Int {
43         var currentPreOrderIndex = currentPreOrderIndex
44         guard let nextPreOrderValue = preorder[safe: currentPreOrderIndex + 1] else {
45             return currentPreOrderIndex
46         }
47 
48         let childDirection = whichChildDirection(inorder: inorder, inorderMap: inorderMap, knownValue: root.val, potentialChildValue: nextPreOrderValue, tooFarValue: tooFarValue)
49 
50         guard let direction = childDirection else {
51             // not a child
52             return currentPreOrderIndex
53         }
54 
55         let childNode = TreeNode(nextPreOrderValue)
56 
57         if direction {
58             // right child
59             root.right = childNode
60             return buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex + 1, root: childNode, tooFarValue: tooFarValue)
61 
62         } else {
63             // left child
64             root.left = childNode
65             currentPreOrderIndex = buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex + 1, root: childNode, tooFarValue: root.val)
66             return buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex, root: root, tooFarValue: tooFarValue)
67         }
68 
69         return currentPreOrderIndex
70     }
71 
72     /**
73      false: left child
74      true: right child
75      nil: neither child
76      */
77     func whichChildDirection(inorder: [Int], inorderMap: [Int: Int], knownValue: Int, potentialChildValue: Int, tooFarValue: Int?) -> Bool? {
78         let potentialChildIndex = inorderMap[potentialChildValue]! // guarenteed to be in the map
79         let knownIndex = inorderMap[knownValue]! // guarenteed to be in the map
80 
81         if potentialChildIndex < knownIndex {
82             return false
83         }
84 
85         if let tooFarValue = tooFarValue, let tooFarIndex = inorderMap[tooFarValue] {
86             if tooFarIndex < potentialChildIndex {
87                 return nil
88             }
89         }
90 
91         return true
92     }
93 }

36ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16         
17         guard preorder.count > 0, inorder.count > 0 else {
18             return nil
19         }
20         
21         var inorderDict = [Int: Int]()
22         for (i, item) in inorder.enumerated() {
23             inorderDict[item] = i
24         }
25         
26         return create(inorderDict, preorder, 0, preorder.count - 1, inorder, 0 , inorder.count - 1)
27 
28     }
29     
30     func create(_ inorderDict: [Int: Int], _ preorder: [Int], _ preLow: Int, _ preHi: Int, _ inorder: [Int], _ inLow: Int, _ inHi: Int) -> TreeNode? {
31         
32         if preLow > preHi {  //debug
33             return nil   
34         }
35         
36         var root = TreeNode(preorder[preLow])
37         let rootIndex = inorderDict[preorder[preLow]]! // debug: dict value is optional, must be unwrapped
38         let leftNum = rootIndex - inLow // debug
39         
40         root.left = create(inorderDict, preorder, preLow + 1, preLow + leftNum, inorder, inLow, rootIndex - 1)
41         root.right = create(inorderDict, preorder, preLow + leftNum + 1, preHi, inorder, rootIndex + 1, inHi)
42         
43         return root
44     }
45 }

44ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16         if preorder.count == 0 {
17             return nil
18         }
19 
20         var map = [Int: Int]()
21         for i in 0..<inorder.count {
22             map[inorder[i]] = i
23         }
24 
25         var stack = [TreeNode]()
26         var value = preorder[0]
27         let root = TreeNode(value)
28 
29         stack.append(root)
30         for i in 1..<preorder.count {
31             value = preorder[i]
32             let node = TreeNode(value)
33             if map[value]! < map[stack.last!.val]! {
34                 stack.last!.left = node
35             } else {
36                 var parent: TreeNode? = nil
37                 while !stack.isEmpty && map[value]! > map[stack.last!.val]! {
38                     parent = stack.removeLast()
39                 }
40                 parent?.right = node
41             }
42             stack.append(node)
43         }
44 
45         return root
46     }
47 }

56ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16     
17         guard !preorder.isEmpty && !inorder.isEmpty else {
18             return nil
19         }
20         
21         return buildTree(preorder, 0, preorder.count-1, inorder, 0, inorder.count-1)
22     }
23     
24     func buildTree(_ preorder: [Int], _ preStart: Int, _ preEnd: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> TreeNode? {
25     
26         guard preStart <= preEnd && inStart <= inEnd else {
27             return nil
28         }
29         
30         var rootVal = preorder[preStart]
31         var root = TreeNode(rootVal)
32         var mid: Int = 0  
33         
34         for i in inStart...inEnd {
35             if inorder[i] == rootVal {
36                 mid = i
37                 break
38             }
39         }
40         
41         root.left = buildTree(preorder, preStart+1, preStart + mid - inStart, inorder, inStart, mid - 1)
42         root.right = buildTree(preorder, preStart + mid - inStart + 1, preEnd, inorder, mid+1, inEnd)
43         return root
44     }
45 }

160ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16         let len = preorder.count
17         if len == 0 { return nil }
18         let root = TreeNode(preorder[0])
19         
20         var i = 0
21         while i < len {
22             if inorder[i] == root.val {
23                 break
24             }
25             i += 1
26         }
27         
28         if i > 0 {
29             root.left = buildTree(Array(preorder[1...i]), Array(inorder[..<i]))    
30         }
31         if i < len-1 {
32             root.right = buildTree(Array(preorder[(i+1)...]), Array(inorder[(i+1)...]))
33         }
34         
35         return root
36     }
37 }

240ms

 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     // 根据中序和前序遍历构建二叉树
16     func buildTree(_ inorder: [Int], _ preorder: [Int]) -> TreeNode? {
17         
18         if inorder.count <= 0 || preorder.count <= 0{
19             return nil
20         }
21         /*
22          *  后序遍历的最后一个节点肯定是整个树的根节点
23          */
24         return buildTrees(preorder, inorder)
25     }
26     
27     func buildTrees(_ inorder: [Int], _ preorder: [Int]) -> TreeNode{
28         
29         // 根据前序遍历的第一个节点作为根节点
30         let root = TreeNode.init(preorder[0])
31         
32         // 根据中序遍历计算根节点左右子节点的个数
33         var indexRoot: Int = -1
34         
35         for index in 0..<inorder.count{
36             if inorder[index] == preorder[0]{
37                 indexRoot = index
38                 break
39             }
40         }
41         
42         // 左子节点的个数
43         let leftNum = indexRoot
44         // 右子节点的个数
45         let rightNum = inorder.count - indexRoot - 1
46         
47         // 生成新的左右子树
48         if indexRoot > 0{
49             let leftNode = buildTrees([Int](inorder[0...indexRoot - 1]), [Int](preorder[1...leftNum]))
50             root.left = leftNode
51         }
52         if indexRoot < inorder.count - 1{
53             let rightNode = buildTrees([Int](inorder[indexRoot + 1...inorder.count - 1]), [Int](preorder[leftNum + 1...leftNum + rightNum]))
54             root.right = rightNode
55         }
56         return root
57     }
58 }

288ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16         
17         if preorder.count == 0 {
18             return nil
19         }
20         
21         if preorder.count == 1 {
22             let val = preorder[0]
23             let root = TreeNode(val)
24             return root
25         }
26         
27         let val = preorder[0]
28         let root = TreeNode(val)
29         
30         var rootIndex = 0
31         for i in 0..<inorder.count {
32             if inorder[i] == val {
33                 rootIndex = i
34             }
35         }
36         
37         var tmpPreorder = [Int]()
38         if rootIndex > 0 {
39             for i in 1...rootIndex {
40                 tmpPreorder.append(preorder[i])
41             }
42         }
43         
44         var tmpInorder = [Int]()
45         for i in 0..<rootIndex {
46             tmpInorder.append(inorder[i])
47         }
48         
49         root.left = buildTree(tmpPreorder, tmpInorder)
50         
51         tmpPreorder = [Int]()
52         for i in rootIndex+1..<preorder.count {
53             tmpPreorder.append(preorder[i])
54         }
55         
56         tmpInorder = [Int]()
57         for i in rootIndex+1..<inorder.count {
58             tmpInorder.append(inorder[i])
59         }
60         
61         root.right = buildTree(tmpPreorder, tmpInorder)
62         
63         return root
64     }
65 }

328ms

 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
16         guard preorder.count != 0, inorder.count != 0, preorder.count == inorder.count else { return nil }
17         let root = TreeNode(preorder[0])
18         let rootInOrderIndex = inorder.index(of: root.val) ?? -1
19         let leftInOrder = Array(inorder[0..<rootInOrderIndex])
20         let leftPreOrderStartIndex = 1
21         let leftPreOrderEndIndexExclusive = leftPreOrderStartIndex + leftInOrder.count
22         let leftPreOrder = Array(preorder[leftPreOrderStartIndex..<leftPreOrderEndIndexExclusive])
23         root.left = buildTree(leftPreOrder, leftInOrder)
24 
25         let rightInOrder = Array(inorder[rootInOrderIndex+1..<inorder.count])
26         let rightPreOrder = Array(preorder[leftPreOrderEndIndexExclusive..<preorder.count])
27         root.right = buildTree(rightPreOrder, rightInOrder)
28         return root
29     }
30 }

332ms

 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  * }
 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋