輸入某二叉樹的前序遍歷和中序遍歷的結果勋又，請重建該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字。
例如廊鸥，
給出前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
給出的數(shù)結點結構如下：
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
根據(jù)樹的遍歷特性壁酬，前序遍歷每次都會訪問根節(jié)點然后訪問左子樹的結點次酌、右子樹幾點。中序遍歷則會先遍歷左子樹節(jié)點舆乔、根節(jié)點岳服、右子樹節(jié)點。所以前序遍歷的結果的第一個數(shù)字就是數(shù)的根節(jié)點希俩。在中序遍歷結果中根節(jié)點的左側數(shù)據(jù)屬于左子樹吊宋、右側數(shù)據(jù)屬于右子樹。
image.png
通過以上三步颜武，可確定三個結點璃搜，第一步確定樹的根節(jié)點拖吼，第二步劃分左右子樹的節(jié)點個數(shù)。第三步確定左右子樹的根節(jié)點（如果左子樹節(jié)點個數(shù)大于0这吻，則前序遍歷中左子樹的根節(jié)點緊跟樹的根節(jié)點吊档。右子樹的根節(jié)點在前序遍歷結果中右子樹的根節(jié)點位域左子樹個數(shù)+1）。接下來我們就可以用遞歸的方式完成重建唾糯。
暴力算法
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
if preorder.count == 0 {
return nil
}
let headValue = preorder.first!
let headNode: TreeNode? = TreeNode(headValue)
for (index,value) in inorder.enumerated() {
if value == headValue {
headNode?.left = buildTree(Array(preorder[1..<index+1]),Array(inorder[0..<index]))
headNode?.right = buildTree(Array(preorder[index+1..<preorder.endIndex]),Array(inorder[index+1..<inorder.endIndex]))
}
}
return headNode
}
遞歸的另一種解法
var inIndex = 0
var preIndex = 0
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
if preorder.count == 0 || inorder.count == 0 {
return nil
}
return build(preorder, inorder,Int.max)
}
func build(_ preorder: [Int], _ inorder: [Int],_ stop: Int) -> TreeNode? {
if preIndex >= preorder.count {
return nil
}
if inorder[inIndex] == stop {
inIndex += 1
return nil
}
let node = TreeNode(preorder[preIndex])
preIndex += 1
node.left = build(preorder, inorder, node.val)
node.right = build(preorder, inorder, stop)
return node
}
