Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

剑指Offer-4.重建二叉树(C++/Java)

silentteller 2019-11-08 18:54:00 阅读数:53 评论数:0 点赞数:0 收藏数:0

程序：

C++

```class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return helper(pre, vin, , pre.size()-, , vin.size()-);
}
TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int leftPre, int rightPre, int leftIn, int rightIn){
if(leftPre > rightPre)
return nullptr;
TreeNode* root = new TreeNode(preorder[leftPre]);
if(leftPre == rightPre)
return root;
else{
int i = leftIn;
for(;i <= rightIn; ++i){
if(inorder[i] == preorder[leftPre])
break;
}
root->left = helper(preorder, inorder, leftPre+, leftPre+i-leftIn, leftIn, i-);
root->right = helper(preorder, inorder, leftPre+i+-leftIn, rightPre, i+, rightIn);
return root;
}
}
};```

Java

```//use HashMap
import java.util.HashMap;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
map = new HashMap<>();
for(int i = 0; i < in.length; ++i){
map.put(in[i], i);
}
return helper(pre, in, 0, pre.length-1, 0, in.length-1);
}
public TreeNode helper(int[] preorder, int[] inorder, int leftPre, int rightPre, int leftIn, int rightIn){
if(leftPre > rightPre)
return null;
TreeNode root = new TreeNode(preorder[leftPre]);
if(leftPre == rightPre)
return root;
else{
int i = map.get(preorder[leftPre]);
root.left = helper(preorder, inorder, leftPre+1, leftPre+i-leftIn, leftIn, i-1);
root.right = helper(preorder, inorder, leftPre+i-leftIn+1, rightPre, i+1, rightIn);
return root;
}
}
private HashMap<Integer, Integer> map;
}```

https://www.cnblogs.com/silentteller/p/11822365.html