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:
- 3
- / 9 20
- / 15 7
根据一棵树的前序遍历与中序遍历构造二叉树.
注意:
你可以假设树中没有重复的元素.
例如, 给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
- 3
- / 9 20
- / 15 7
- 32ms
- // /**
- //* Definition for a binary tree node.
- //* 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
- //* }
- //* }
- //*/
- extension Array {
- subscript(safe index: Int) -> Element? {
- guard index>= 0 && index <self.count else {
- return nil
- }
- return self[index]
- }
- }
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- guard let rootValue = preorder[safe: 0] else {
- return nil
- }
- var inorderMap: [Int: Int] = [:]
- for index in 0..<inorder.count {
- inorderMap[inorder[index]] = index
- }
- let root = TreeNode(rootValue)
- buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: 0, root: root, tooFarValue: nil)
- return root
- }
- func buildNextNode(inorder: [Int], preorder: [Int], inorderMap: [Int: Int], currentPreOrderIndex: Int, root: TreeNode, tooFarValue: Int?) -> Int {
- var currentPreOrderIndex = currentPreOrderIndex
- guard let nextPreOrderValue = preorder[safe: currentPreOrderIndex + 1] else {
- return currentPreOrderIndex
- }
- let childDirection = whichChildDirection(inorder: inorder, inorderMap: inorderMap, knownValue: root.val, potentialChildValue: nextPreOrderValue, tooFarValue: tooFarValue)
- guard let direction = childDirection else {
- // not a child
- return currentPreOrderIndex
- }
- let childNode = TreeNode(nextPreOrderValue)
- if direction {
- // right child
- root.right = childNode
- return buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex + 1, root: childNode, tooFarValue: tooFarValue)
- } else {
- // left child
- root.left = childNode
- currentPreOrderIndex = buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex + 1, root: childNode, tooFarValue: root.val)
- return buildNextNode(inorder: inorder, preorder: preorder, inorderMap: inorderMap, currentPreOrderIndex: currentPreOrderIndex, root: root, tooFarValue: tooFarValue)
- }
- return currentPreOrderIndex
- }
- /**
- false: left child
- true: right child
- nil: neither child
- */
- func whichChildDirection(inorder: [Int], inorderMap: [Int: Int], knownValue: Int, potentialChildValue: Int, tooFarValue: Int?) -> Bool? {
- let potentialChildIndex = inorderMap[potentialChildValue]! // guarenteed to be in the map
- let knownIndex = inorderMap[knownValue]! // guarenteed to be in the map
- if potentialChildIndex <knownIndex {
- return false
- }
- if let tooFarValue = tooFarValue, let tooFarIndex = inorderMap[tooFarValue] {
- if tooFarIndex < potentialChildIndex {
- return nil
- }
- }
- return true
- }
- }
- 36ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- guard preorder.count> 0, inorder.count> 0 else {
- return nil
- }
- var inorderDict = [Int: Int]()
- for (i, item) in inorder.enumerated() {
- inorderDict[item] = i
- }
- return create(inorderDict, preorder, 0, preorder.count - 1, inorder, 0 , inorder.count - 1)
- }
- func create(_ inorderDict: [Int: Int], _ preorder: [Int], _ preLow: Int, _ preHi: Int, _ inorder: [Int], _ inLow: Int, _ inHi: Int) -> TreeNode? {
- if preLow> preHi { //debug
- return nil
- }
- var root = TreeNode(preorder[preLow])
- let rootIndex = inorderDict[preorder[preLow]]! // debug: dict value is optional, must be unwrapped
- let leftNum = rootIndex - inLow // debug
- root.left = create(inorderDict, preorder, preLow + 1, preLow + leftNum, inorder, inLow, rootIndex - 1)
- root.right = create(inorderDict, preorder, preLow + leftNum + 1, preHi, inorder, rootIndex + 1, inHi)
- return root
- }
- }
- 44ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- if preorder.count == 0 {
- return nil
- }
- var map = [Int: Int]()
- for i in 0..<inorder.count {
- map[inorder[i]] = i
- }
- var stack = [TreeNode]()
- var value = preorder[0]
- let root = TreeNode(value)
- stack.append(root)
- for i in 1..<preorder.count {
- value = preorder[i]
- let node = TreeNode(value)
- if map[value]! <map[stack.last!.val]! {
- stack.last!.left = node
- } else {
- var parent: TreeNode? = nil
- while !stack.isEmpty && map[value]!> map[stack.last!.val]! {
- parent = stack.removeLast()
- }
- parent?.right = node
- }
- stack.append(node)
- }
- return root
- }
- }
- 56ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- guard !preorder.isEmpty && !inorder.isEmpty else {
- return nil
- }
- return buildTree(preorder, 0, preorder.count-1, inorder, 0, inorder.count-1)
- }
- func buildTree(_ preorder: [Int], _ preStart: Int, _ preEnd: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> TreeNode? {
- guard preStart <= preEnd && inStart <= inEnd else {
- return nil
- }
- var rootVal = preorder[preStart]
- var root = TreeNode(rootVal)
- var mid: Int = 0
- for i in inStart...inEnd {
- if inorder[i] == rootVal {
- mid = i
- break
- }
- }
- root.left = buildTree(preorder, preStart+1, preStart + mid - inStart, inorder, inStart, mid - 1)
- root.right = buildTree(preorder, preStart + mid - inStart + 1, preEnd, inorder, mid+1, inEnd)
- return root
- }
- }
- 160ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- let len = preorder.count
- if len == 0 { return nil }
- let root = TreeNode(preorder[0])
- var i = 0
- while i <len {
- if inorder[i] == root.val {
- break
- }
- i += 1
- }
- if i> 0 {
- root.left = buildTree(Array(preorder[1...i]), Array(inorder[..<i]))
- }
- if i <len-1 {
- root.right = buildTree(Array(preorder[(i+1)...]), Array(inorder[(i+1)...]))
- }
- return root
- }
- }
- 240ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- // 根据中序和前序遍历构建二叉树
- func buildTree(_ inorder: [Int], _ preorder: [Int]) -> TreeNode? {
- if inorder.count <= 0 || preorder.count <= 0{
- return nil
- }
- /*
- * 后序遍历的最后一个节点肯定是整个树的根节点
- */
- return buildTrees(preorder, inorder)
- }
- func buildTrees(_ inorder: [Int], _ preorder: [Int]) -> TreeNode{
- // 根据前序遍历的第一个节点作为根节点
- let root = TreeNode.init(preorder[0])
- // 根据中序遍历计算根节点左右子节点的个数
- var indexRoot: Int = -1
- for index in 0..<inorder.count{
- if inorder[index] == preorder[0]{
- indexRoot = index
- break
- }
- }
- // 左子节点的个数
- let leftNum = indexRoot
- // 右子节点的个数
- let rightNum = inorder.count - indexRoot - 1
- // 生成新的左右子树
- if indexRoot> 0{
- let leftNode = buildTrees([Int](inorder[0...indexRoot - 1]), [Int](preorder[1...leftNum]))
- root.left = leftNode
- }
- if indexRoot <inorder.count - 1{
- let rightNode = buildTrees([Int](inorder[indexRoot + 1...inorder.count - 1]), [Int](preorder[leftNum + 1...leftNum + rightNum]))
- root.right = rightNode
- }
- return root
- }
- }
- 288ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- if preorder.count == 0 {
- return nil
- }
- if preorder.count == 1 {
- let val = preorder[0]
- let root = TreeNode(val)
- return root
- }
- let val = preorder[0]
- let root = TreeNode(val)
- var rootIndex = 0
- for i in 0..<inorder.count {
- if inorder[i] == val {
- rootIndex = i
- }
- }
- var tmpPreorder = [Int]()
- if rootIndex> 0 {
- for i in 1...rootIndex {
- tmpPreorder.append(preorder[i])
- }
- }
- var tmpInorder = [Int]()
- for i in 0..<rootIndex {
- tmpInorder.append(inorder[i])
- }
- root.left = buildTree(tmpPreorder, tmpInorder)
- tmpPreorder = [Int]()
- for i in rootIndex+1..<preorder.count {
- tmpPreorder.append(preorder[i])
- }
- tmpInorder = [Int]()
- for i in rootIndex+1..<inorder.count {
- tmpInorder.append(inorder[i])
- }
- root.right = buildTree(tmpPreorder, tmpInorder)
- return root
- }
- }
- 328ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- guard preorder.count != 0, inorder.count != 0, preorder.count == inorder.count else { return nil }
- let root = TreeNode(preorder[0])
- let rootInOrderIndex = inorder.index(of: root.val) ?? -1
- let leftInOrder = Array(inorder[0..<rootInOrderIndex])
- let leftPreOrderStartIndex = 1
- let leftPreOrderEndIndexExclusive = leftPreOrderStartIndex + leftInOrder.count
- let leftPreOrder = Array(preorder[leftPreOrderStartIndex..<leftPreOrderEndIndexExclusive])
- root.left = buildTree(leftPreOrder, leftInOrder)
- let rightInOrder = Array(inorder[rootInOrderIndex+1..<inorder.count])
- let rightPreOrder = Array(preorder[leftPreOrderEndIndexExclusive..<preorder.count])
- root.right = buildTree(rightPreOrder, rightInOrder)
- return root
- }
- }
- 332ms
- /**
- * Definition for a binary tree node.
- * 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
- * }
- * }
- */
- class Solution {
- func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
- var inorder = inorder
- var preorder = preorder
- var root: TreeNode
- if preorder.count < 1{
- return nil
- }
- let first = preorder.removeFirst()
- root = TreeNode(first)
- let index = inorder.index(of: first)!
- let lin = Array(inorder[0..<index])
- let lpro = Array(preorder[0..<index])
- root.left = buildTree(lpro, lin)
- let rin = Array(inorder[(index+1)...])
- let rpro = Array(preorder[index...])
- root.right = buildTree(rpro, rin)
- return root
- }
- }
[Swift]LeetCode105. 从前序与中序遍历序列构造二叉树 | Construct Binary Tree from Preorder and Inorder Traversal
来源: http://www.bubuko.com/infodetail-2844947.html