forked from JiauZhang/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path04_construct_binary_tree.cpp
More file actions
109 lines (93 loc) · 3.77 KB
/
Copy path04_construct_binary_tree.cpp
File metadata and controls
109 lines (93 loc) · 3.77 KB
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
* Copyright(c) 2019 Jiau Zhang
* For more information see <https://github.com/JiauZhang/algorithms>
*
* This repo is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation
*
* It is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with THIS repo. If not, see <http://www.gnu.org/licenses/>.
*/
/**
*题目描述
* 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
* 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
* 则重建二叉树并返回。
*
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
解题思路：
前序遍历：根节点->左节点->右节点
中序遍历：左节点->根节点->右节点
所以前序遍历的第一个数就根节点，中序遍历中的根节点左边的
就是左子树，右边的是右子树，递归解决即可。
*/
/* 该方法需要来回复制vector，浪费内存 */
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() == 0 || pre.size() ==0)
return NULL;
TreeNode *root = new TreeNode(pre[0]);
vector<int> left_pre, left_vin;
vector<int> right_pre, right_vin;
bool flag = 0;
int length = pre.size();
for (int i=0; i<length; i++) {
if (vin[i] != pre[0] && flag == 0) {
left_vin.push_back(vin[i]);
left_pre.push_back(pre[i+1]);
} else if (flag == 0) {
flag = 1;
} else {
right_vin.push_back(vin[i]);
right_pre.push_back(pre[i]);
}
}
TreeNode *pLeft = reConstructBinaryTree(left_pre, left_vin);
TreeNode *pRight = reConstructBinaryTree(right_pre, right_vin);
root->left = pLeft;
root->right = pRight;
return root;
}
};
/* 在vector中就地比较，不需要复制，能节省内存 */
class Solution {
public:
TreeNode *reConstruct(vector<int> &pre, int pstart, int pend, \
vector<int> &vin, int vstart, int vend) {
if (pstart>=pend || vstart>=vend)
return NULL;
TreeNode *root = new TreeNode(pre[pstart]);
int vin_start = vstart;
for (; vin_start<vend; vin_start++) {
if (vin[vin_start] == pre[pstart])
break;
}
int dv = vin_start - vstart;
/* 前序中左子树和右子树是紧挨着的，所以首尾相接 */
/* 中序中左右子树是被更节点分开的，所以索引值并不连续 */
TreeNode *pLeft = reConstruct(pre, pstart+1, pstart+dv+1, vin, vstart, vin_start);
TreeNode *pRight = reConstruct(pre, pstart+dv+1, pend, vin, vin_start+1, vend);
root->left = pLeft;
root->right = pRight;
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() == 0 || pre.size() ==0)
return NULL;
return reConstruct(pre, 0, pre.size(), vin, 0, vin.size());
}
};