LeetCode105. 从前序与中序遍历序列构造二叉树

 1 class Solution {
 2 public:
 3     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
 4         if(preorder.size() ==  0) return NULL;
 5         //找根结点
 6         int rootValue = preorder[0];
 7         TreeNode *root = new TreeNode(rootValue);
 8         if(preorder.size() == 1) return root;
 9 
10         //找到根结点在中序数组中的位置，作为分割点
11         int Index;
12         for(int i = 0;i < inorder.size();i++){
13             if(rootValue == inorder[i]) {Index = i;break;}
14         }
15 
16         //对中序数组进行分割，左闭右开原则
17         vector<int>leftInorder(inorder.begin(),inorder.begin()+Index);  //[0,Index)
18         vector<int>rightInorder(inorder.begin()+Index+1,inorder.end()); //[Index+1,end)
19 
20         //对前序数组进行分割，左闭右开原则,用中序分割后的左右数组个数来分割前序数组
21         preorder.erase(preorder.begin()); //开头元素没有用，舍弃
22         vector<int>leftPreorder(preorder.begin(),preorder.begin()+leftInorder.size());
23         //[0,leftInorder.size)
24         vector<int>rightPreorder(preorder.begin()+leftInorder.size(),preorder.end());
25         //[leftInorder.size(),preorder.end)
26         
27         //递归处理左、右
28         root->left = buildTree(leftPreorder,leftInorder);
29         root->right = buildTree(rightPreorder,rightInorder);
30         return root;
31     }
32 };