★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {16 let instart = 017 let inend = inorder.count - 118 let poststart = 019 let postend = postorder.count - 120 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 nil25 }26 let rootValue = postorder[postend]27 let root = TreeNode(rootValue)28 var k = 029 for i in 0.. 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 = nil10 * self.right = nil11 * }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 nil18 }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 nil26 }27 28 let root = TreeNode(postorder[postEnd])29 30 var mid = 031 for i in inStart...inEnd where inorder[i] == root.val {32 mid = i33 break34 }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 root40 }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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 // 根据中序和后序遍历构建二叉树16 func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {17 if inorder.count <= 0 || postorder.count <= 0{18 return nil19 }20 /*21 * 后序遍历的最后一个节点肯定是整个树的根节点22 */23 return buildTrees(inorder, postorder)24 }25 26 func buildTrees(_ inorder: [Int], _ postorder: [Int]) -> TreeNode{27 28 let postorderRight = postorder.count - 129 // 根据后续遍历的最后一个节点作为根节点30 let root = TreeNode.init(postorder[postorderRight])31 32 // 根据中序遍历计算根节点左右子节点的个数33 var indexRoot: Int = -134 35 for index in 0.. 0{49 let leftNode = buildTrees([Int](inorder[0...indexRoot - 1]), [Int](postorder[0...leftNum - 1]))50 root.left = leftNode51 }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 = rightNode55 }56 57 return root58 }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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {16 let len = postorder.count17 if len == 0 { return nil }18 let root = TreeNode(postorder.last!)19 var i = 020 while i < len {21 if inorder[i] == root.val {22 break23 }24 i += 125 }26 27 if i > 0 {28 root.left = buildTree(Array(inorder[.. 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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {16 17 if postorder.count == 0 {18 return nil19 }20 21 if postorder.count == 1 {22 let val = postorder[postorder.count - 1]23 let root = TreeNode(val)24 return root25 }26 27 let val = postorder[postorder.count - 1]28 let root = TreeNode(val)29 30 var rootIndex = 031 for i in 0.. 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 = nil10 * self.right = nil11 * }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 node30 }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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {16 if inorder.count == 0 || postorder.count == 0 {17 return nil18 }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.. = 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.. 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 = nil10 * self.right = nil11 * }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 nil18 }19 20 let root = TreeNode(postorder.last!)21 let index = inorder.index(of: postorder.last!)!22 root.left = buildTree([Int](inorder[..