leetcode-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.

分析


二叉树的前、中、后3种遍历序列中的前中,中后两对遍历序列可以唯一确定一颗二叉树。对于本题目,根据前序遍历和中序遍历的二叉树构建二叉树,可以先用一个具体的例子来思考,来确定边界值。例如一个二叉树的先序遍历输出序列是:A, B, C, D, E, F, G, H,中序遍历输出序列是:C, B, E, D, F, A, H, G。可以确定的是,A 是根节点,而从中序遍历的序列来看,C, B, E, D, F 在根节点的左边,H, G 在根节点的右边,先序遍历的序列去掉 A 之后,同样可以分成两拨,而且两拨的第一个节点都是根节点,分别是 C,H,到这已经很清楚了,这是一个递归的过程。

解决方案1(C++)


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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTreeWithPreandIn(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
TreeNode* buildTreeWithPreandIn(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end) {
if(pre_start > pre_end) {
return NULL;
}
int pre_first_result = preorder[pre_start];
int root_position = in_start;
for (; root_position < in_end; root_position++) {
if(inorder[root_position] == pre_first_result) {
break;
}
}
TreeNode* node = new TreeNode(pre_first_result);
int left_length = root_position - in_start;
int right_length = in_end - root_position;
node->left = buildTreeWithPreandIn(preorder, inorder, pre_start+1, pre_start+left_length, in_start, root_position-1);
node->right = buildTreeWithPreandIn(preorder, inorder, pre_end-right_length+1, pre_end, root_position+1, in_end);
return node;
}
};

解决方案2(Java)


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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeWithPreandIn(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode buildTreeWithPreandIn(int[] preorder, int[] inorder, int pre_start, int pre_end, int in_start, int in_end) {
if(pre_start > pre_end) {
return null;
}
int pre_first_result = preorder[pre_start];
int root_position = in_start;
for (; root_position < in_end; root_position++) {
if(inorder[root_position] == pre_first_result) {
break;
}
}
TreeNode node = new TreeNode(pre_first_result);
int left_length = root_position - in_start;
int right_length = in_end - root_position;
node.left = buildTreeWithPreandIn(preorder, inorder, pre_start+1, pre_start+left_length, in_start, root_position-1);
node.right = buildTreeWithPreandIn(preorder, inorder, pre_end-right_length+1, pre_end, root_position+1, in_end);
return node;
}
}

解决方案3(Golang)


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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(inorder) == 0 {
return nil
}
res := &TreeNode{
Val: preorder[0],
}
if len(inorder) == 1 {
return res
}
index := indexOf(res.Val, inorder)
res.Left = buildTree(preorder[1:index+1], inorder[:index])
res.Right = buildTree(preorder[index+1:], inorder[index+1:])
return res
}
func indexOf(val int, nums []int) int {
for i, v := range nums {
if v == val {
return i
}
}
return 0
}

相关问题


(M) Construct Binary Tree from Inorder and Postorder Traversal

题目来源