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

[Swift]LeetCode106.从中序与后序遍历序列构造二叉树|ConstructBinaryTreefromInorder ...

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

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

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

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

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

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

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

For example, given

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

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

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

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

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

108ms
 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(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
16         let instart = 0
17         let inend = inorder.count - 1
18         let poststart = 0
19         let postend = postorder.count - 1
20         return buildTree(inorder, instart, inend, postorder, poststart, postend)
21     }
22     private func buildTree(_ inorder: [Int], _ instart: Int, _ inend: Int, _ postorder: [Int], _ poststart: Int, _ postend: Int )-> TreeNode? {
23         if instart > inend || poststart > postend {
24             return nil
25         }
26         let rootValue = postorder[postend]
27         let root = TreeNode(rootValue)
28         var k = 0
29         for i in 0..<inorder.count {
30             if inorder[i] == rootValue {
31                 k = i
32                 break
33             }
34         }
35         root.left = buildTree(inorder, instart, k - 1, postorder, poststart, poststart + k - 1 - instart)
36         root.right = buildTree(inorder, k + 1, inend, postorder, poststart + k - instart, postend - 1)
37         return root
38     }
39 }

116ms

 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(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
16          guard inorder.count > 0 && postorder.count > 0 && inorder.count == postorder.count else {
17             return nil
18         }
19         
20         return _buildHelper(inorder, 0, inorder.count - 1, postorder, 0, postorder.count - 1)
21     }
22     
23     func _buildHelper(_ inorder: [Int], _ inStart: Int, _ inEnd: Int, _ postorder: [Int], _ postStart: Int, _ postEnd: Int) -> TreeNode? {
24         guard inStart <= inEnd && postStart <= postEnd else {
25             return nil
26         }
27         
28         let root = TreeNode(postorder[postEnd])
29         
30         var mid = 0
31         for i in inStart...inEnd where inorder[i] == root.val {
32             mid = i
33             break
34         }
35         
36         root.left = _buildHelper(inorder, inStart, mid - 1, postorder, postStart, mid - 1 - inStart + postStart)
37         root.right = _buildHelper(inorder, mid + 1, inEnd, postorder, mid - inStart + postStart, postEnd - 1)
38         
39         return root
40     }
41 }

156ms

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

156ms

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

248ms

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

316ms

 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(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
16         guard inorder.count > 0 && postorder.count > 0 else { return nil }
17         let node = TreeNode(postorder.last!)
18         let index = inorder.firstIndex(of: node.val)!
19 
20         let inLeft = Array(inorder[0 ..< index])
21         let inRight = Array(inorder[index + 1 ..< inorder.count])
22 
23         let postLeft = Array(postorder[0 ..< index])
24         let postRight = Array(postorder[index ..< postorder.count - 1])
25 
26         node.left = buildTree(inLeft, postLeft)
27         node.right = buildTree(inRight, postRight)
28 
29         return node
30     }
31 }

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

392ms

 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(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
16         guard !inorder.isEmpty && !postorder.isEmpty && inorder.count == postorder.count else {
17             return nil
18         }
19         
20         let root = TreeNode(postorder.last!)
21         let index = inorder.index(of: postorder.last!)!
22         root.left = buildTree([Int](inorder[..<index]), [Int](postorder[..<index]))
23         root.right = buildTree([Int](inorder[(index+1)...]), [Int](postorder[index..<(postorder.count-1)]))
24         
25         return root
26     }
27 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode959.由斜杠划分区域|RegionsCutBySlashes发布时间:2022-07-14
下一篇:
行走于Swift的世界中(转)发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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