Construct Binary Tree

105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述

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

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

题目大意

根据前序和中序,构建二叉树。

解题思路

由于前序遍历的规则是:根->左->右,所以前序遍历的第一个元素为根节点,根据这一特性,将中序数组分为左子树和右子树。重复以上操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 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 dict = [Int: Int]() //参考leetcode上的最优解决方案,优化
for (i, n) in inorder.enumerated() {
dict[n] = i
}
func build(preIndex: Int, start: Int, end: Int) -> TreeNode? {
guard start <= end else { return nil }
let root = TreeNode(preorder[preIndex])
let index = dict[preorder[preIndex]] ?? 0
if index > start {
root.left = build(preIndex: preIndex + 1, start: start, end: index - 1)
}
if index < end {
//由于preIndex + 1之后,首元素其实是左子树,所以需要加上当前inorder数组中,左子树的个数,才能将首元素变为右子树。
root.right = build(preIndex: preIndex + index - start + 1, start: index + 1, end: end)
}
return root
}
return build(preIndex: 0, start: 0, end: inorder.count - 1)
}
}

106. Construct Binary Tree from Inorder and Postorder Traversal

题目描述

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

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

题目大意

根据后序和中序,构建二叉树

解题思路

与前序和中序构建树的思路差不多。
需要使用后序特性,最后一个数为根节点。将前序数组分为左右两个子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 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], _ postorder: [Int]) -> TreeNode? {
var dict = [Int: Int]() //参考leetcode上的最优解决方案,优化
for (i, n) in inorder.enumerated() {
dict[n] = i
}
func build(postStart: Int, postEnd: Int, inStart: Int, inEnd: Int) -> TreeNode? {
guard inStart <= inEnd && postStart <= postEnd else { return nil }
let root = TreeNode(postorder[postEnd])
let index = dict[postorder[postEnd]] ?? 0
if index > inStart {
root.left = build(postStart: postStart, postEnd: postStart + index - inStart - 1, inStart: inStart, inEnd: index - 1)
}
if index < inEnd {
root.right = build(postStart: postStart + index - inStart, postEnd: postEnd - 1, inStart: index + 1, inEnd: inEnd)
}
return root
}
return build(postStart: 0, postEnd: postorder.count - 1, inStart: 0, inEnd: inorder.count - 1)
}
}
0%