Note: This article is available in Chinese only. 本文暂无英文版本。
View original
思路：
分治搞之。
实际上两个vector就够了。。。4个会MLE(在leetcode上。。。
代码实现
1/**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10class Solution {
11public:
12 TreeNode* res;
13 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
14 int siz = pre.size();
15 if (siz==0) return NULL;
16 int rt = pre[0];
17 int pos=-1;
18 for ( int i = 0 ; i < siz; i++)
19 if (vin[i]==rt)
20 {
21 pos = i;
22 break;
23 }
24 vector<int>preL,preR,vinL,vinR;
25 for ( int i = 0 ; i < pos ; i++)
26 {
27 preL.push_back(pre[i+1]);
28 vinL.push_back(vin[i]);
29 }
30 for ( int i = pos + 1 ; i < siz ; i++)
31 {
32 preR.push_back(pre[i]);
33 vinR.push_back(vin[i]);
34 }
35 TreeNode *head = new TreeNode(rt);
36 head->left = reConstructBinaryTree(preL,vinL);
37 head->right = reConstructBinaryTree(preR,vinR);
38 return head;
39
40
41 }
42};
43
44
45
46
47/* ***********************************************
48Author :111qqz
49Created Time :2017年04月05日 星期三 16时21分35秒
50File Name :105.cpp
51************************************************ */
52/**
53
54 * Definition for a binary tree node.
55
56 * struct TreeNode {
57
58 * int val;
59
60 * TreeNode *left;
61
62 * TreeNode *right;
63
64 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
65
66 * };
67
68 */
69
70class Solution {
71
72public:
73
74 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
75
76 int siz = preorder.size();
77 if (siz==0) return NULL;
78 int rt = preorder[0];
79 int pos;
80 for ( int i = 0 ; i < siz ; i++)
81 {
82 if (inorder[i]==rt)
83 {
84 pos = i;
85 break;
86 }
87 }
88 vector<int>preL,inL;
89 TreeNode *head = new TreeNode(rt);
90 for ( int i = 0 ; i < pos ; i++)
91 {
92 preL.push_back(preorder[i+1]);
93 inL.push_back(inorder[i]);
94 }
95 head->left = buildTree(preL,inL);
96
97 preL.clear();
98 inL.clear();
99 for ( int i = pos + 1 ; i < siz; i++)
100 {
101 preL.push_back(preorder[i]);
102 inL.push_back(inorder[i]);
103 }
104 head->right = buildTree(preL,inL);
105 return head;
106
107 }
108
109};