剑指Offer07 重建二叉树

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
13         int n=preorder.size();
14         if(!n) return nullptr;
15         int* ptrpreorder=&preorder[0];
16         int* ptrinorder=&inorder[0];
17         return Construct(ptrpreorder,ptrpreorder+n-1,ptrinorder,ptrinorder+n-1);
18     }
19 
20     TreeNode* Construct(int* startpreorder, int* endpreorder, int* startinorder, int*endinorder){
21         int rootval=startpreorder[0];
22         TreeNode* curroot= new TreeNode();
23         curroot->val=rootval;
24         curroot->left=curroot->right=nullptr;
25 
26         if(startpreorder==endpreorder){
27             if(startinorder==endinorder && *startpreorder==*startinorder)
28                 return curroot;
29         }
30 
31         int* rootinorder=startinorder;
32         while(rootinorder<=endinorder && *rootinorder!=rootval)
33             rootinorder++;
34         
35         int leftlen=0,rightlen=0;
36         leftlen=rootinorder-startinorder;
37         int* leftendpreorder=startpreorder+leftlen;
38         if(leftlen){
39             curroot->left=Construct(startpreorder+1,leftendpreorder,startinorder,rootinorder-1);
40         }
41 
42         if(rootinorder!=endinorder){
43             curroot->right=Construct(leftendpreorder+1,endpreorder,rootinorder+1,endinorder);
44         }
45         return curroot;
46     }
47 };