题目描述
Given preorder and inorder traversal of a tree, construct the binary tree.
NOTE
You may assume that duplicates do not exist in the tree.
Example:
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
解题思路
- 主要是分为左右两个序列，然后递归建树。
- 构造左右子树的各自序列，然后递归
C++代码
/**
* 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) {
if(preorder.size() == 0 || inorder.size() == 0){
return NULL;
}
TreeNode* root = new TreeNode(preorder[0]);
int t = preorder[0];
int idx = 0;
for(int i = 0; i < inorder.size(); i++){
if(inorder[i] == t){
idx = i;
}
}
vector<int> left_pre, left_in;
vector<int> right_pre, right_in;
for(int i = 0; i < idx; i++){
left_pre.push_back(preorder[i + 1]);
left_in.push_back(inorder[i]);
}
for(int i = idx + 1; i < preorder.size(); i++){
right_pre.push_back(preorder[i]);
right_in.push_back(inorder[i]);
}
root -> left = buildTree(left_pre, left_in);
root -> right = buildTree(right_pre, right_in);
return root;
}
};
第二遍解题思路
- 使用一个全局的index，表示此时根的位置
- 将中序遍历分为左右两个部分，进行递归建树。
C++代码
/**
* 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:
int index = 0;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
index = 0;
return build_helper(preorder, inorder, 0, preorder.size() - 1);
}
TreeNode* build_helper(vector<int>& preorder, vector<int>& inorder, int begin, int end){
if(end < begin){
return NULL;
}
int t = preorder[index];
index++;
TreeNode* root = new TreeNode(t);
int idx = findIdx(inorder, t, begin, end);
root -> left = build_helper(preorder, inorder, begin, idx - 1); //把中序分为左右两个部分
root -> right = build_helper(preorder, inorder, idx + 1, end);
return root;
}
int findIdx(vector<int> inorder, int target, int begin, int end){
for(int i = begin; i <= end; i++){
if(inorder[i] == target){
return i;
}
}
return -1;
}
};
200207解题思路
- 左右子树 递归建树
- 需要有一个辅助函数，里面有四个参数 preorder， inorder， begin， end
- 除此之外，还需要有index，表示preorder走到了哪里
- 然后找到 preorder[index] 在inorder中的位置，将其划分成两个左右范围，以pos返回。
- root -> left 建树的范围为 begin， pos - 1
- root -> right 建树的范围为 pos + 1， end
C++代码
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int idx = 0;
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size() == 0 || vin.size() == 0){
return NULL;
}
return fun_helper(pre, vin, 0, pre.size() - 1);
}
TreeNode* fun_helper(vector<int> pre, vector<int> vin, int begin, int end){
if(begin > end){
return NULL;
}
int val = pre[idx];
idx++;
TreeNode* root = new TreeNode(val);
int pos = begin;
while(vin[pos] != val){
pos++;
}
root -> left = fun_helper(pre, vin, begin, pos - 1);
root -> right = fun_helper(pre, vin, pos + 1, end);
return root;
}
};
