[Swift]LeetCode889. 根据前序和后序遍历构造二叉树 | Construct Binary Tree from Preorder and Postorder Traversal

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

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

20ms

 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     private var pre = [Int]()
16     private var post = [Int]()
17     
18     func constructFromPrePost(_ pre: [Int], _ post: [Int]) -> TreeNode? {
19         guard pre.count == post.count else { return nil }
20         guard pre.count > 0 else { return nil }
21         self.pre = pre
22         self.post = post
23         
24         return helper(0, 0, pre.count)
25     }
26     
27     private func helper(_ preStart: Int, _ postStart: Int, _ length: Int) -> TreeNode? {
28         guard length > 0 else { return nil }
29         
30         let currentRoot = TreeNode(pre[preStart])
31         
32         guard length > 1 else { return currentRoot }
33         
34         var leftChildIndexInPost = 0
35         for i in postStart..<(postStart + length) {
36             if post[i] == pre[preStart + 1] {
37                 leftChildIndexInPost = i
38                 break
39             }
40         }
41         
42         let l = leftChildIndexInPost - postStart + 1
43         
44         
45         currentRoot.left = helper(preStart + 1, postStart, l)
46         currentRoot.right = helper(preStart + 1 + l, leftChildIndexInPost + 1, length - l - 1)
47         
48         return currentRoot
49     }
50 }

28ms

 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 construct(_ pre: [Int], _ i: inout Int, _ pos: [Int], _ j: inout Int) -> TreeNode? {
16         guard i < pre.count else { return nil }
17        
18         let node = TreeNode(pre[i])
19         i += 1
20         
21         if node.val != pos[j] {
22             node.left = construct(pre, &i, pos, &j)
23         }
24         if node.val != pos[j] {
25             node.right = construct(pre, &i, pos, &j)
26         }
27         j += 1
28         return node
29     }
30     func constructFromPrePost(_ pre: [Int], _ pos: [Int]) -> TreeNode? {
31         var i = 0, j = 0
32         return construct(pre, &i, pos, &j)
33     }
34 }

Runtime: 36 ms

Memory Usage: 19.2 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 constructFromPrePost(_ pre: [Int], _ post: [Int]) -> TreeNode? {
16         var s:[TreeNode?] = [TreeNode?]()
17         s.append(TreeNode(pre[0]))
18         var i:Int = 1
19         var j:Int = 0
20         while(i < pre.count)
21         {
22             var node = TreeNode(pre[i])
23             while(s.count != 0 && s[s.count - 1]!.val == post[j])
24             {
25                 s.popLast()
26                 j += 1
27             }
28             if s[s.count - 1]?.left == nil
29             {
30                 s[s.count - 1]?.left = node
31             }
32             else
33             {
34                 s[s.count - 1]?.right = node
35             }
36             s.append(node)
37             i += 1
38         }
39         return s[0]      
40     }
41 }

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     var root: TreeNode?
16     
17     func constructFromPrePost(_ pre: [Int], _ post: [Int]) -> TreeNode? {
18         if pre.count == 0 {
19             return nil
20         } else if pre.count == 1 {
21             return TreeNode(pre[0])
22         }
23         
24         var pre = pre
25         var post = post
26         
27         let node = TreeNode(pre[0])
28         pre.remove(at: 0)
29         post.remove(at: post.count - 1)
30         
31         let index = post.index(of: pre[0]) ?? 0
32         let leftPost = Array(post[0...index])
33         let leftPre = Array(pre[0..<leftPost.count])
34         let rightPost = Array(post[(index + 1)..<post.count])
35         let rightPre = Array(pre[leftPost.count..<pre.count])
36         
37         node.left = constructFromPrePost(leftPre, leftPost)
38         node.right = constructFromPrePost(rightPre, rightPost)
39         
40         return node
41     }
42 }

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 constructFromPrePost(_ pre: [Int], _ post: [Int]) -> TreeNode? {
16         if pre.count == 0 || post.count == 0 {
17             return nil;
18         }
19         let root = TreeNode(pre.first!)
20         if pre.count >= 2 {
21             let leftKey = pre[1]
22             for (index, value) in post.enumerated() {
23                 if value == leftKey {
24                     let leftNodeCount = index + 1
25                     root.left = constructFromPrePost(Array(pre[1 ..< leftNodeCount + 1]), Array(post[0 ..< leftNodeCount]))
26                     root.right = constructFromPrePost(Array(pre[leftNodeCount + 1 ..< pre.count]), Array(post[leftNodeCount ..< post.count - 1]))
27                 }
28             }
29         }
30         return root
31     }
32 }