LeetCode106. 从中序与后序遍历序列构造二叉树

题目

代码

 1 class Solution {
 2 public:
 3    
 4     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
 5         //第一步
 6         if(postorder.size() == 0) return NULL;
 7 
 8         //第二步,后序数组的最后一个元素就是当前元素
 9         int rootValue = postorder[postorder.size()-1];
10         TreeNode *root = new TreeNode(rootValue);
11         if(postorder.size() == 1) return root; //只有一个根节点
12 
13         //第三步,找到后序数组最后一个元素在中序数组的位置，作为切割点
14         int Index;
15         for(Index = 0;Index < inorder.size();Index++){
16             if(inorder[Index] == rootValue) break;
17         }
18         
19         //第四步,切割中序数组，得到中序左数组、中序右数组
20         //采用左闭右开，[0,Index)
21         vector<int>leftInorder(inorder.begin(),inorder.begin()+Index);
22         //[Index+1,end)
23         vector<int>rightInorder(inorder.begin()+Index+1 ,inorder.end());
24 
25         //第五步,切割后序数组，得到后序左数组，后序右数组
26         postorder.pop_back(); //舍弃最后一个元素 postorder.erase(postorder.end()-1) 参数为迭代器 
27         //采用左闭右开
28         //[0,leftInorder.size)
29         vector<int>leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
30         //[leftInorder.size,postorder.size)
31         vector<int>rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
32 
33         //第六步,递归处理左、右
34         root->left = buildTree(leftInorder,leftPostorder);
35         root->right = buildTree(rightInorder,rightPostorder);
36         return root;
37     }
38 };

注意：

1.stl 中 vector 赋初值的方法：https://www.cnblogs.com/quyc/p/12857054.html

2. stl 中的容器和算法都是左闭右开的 https://www.zhihu.com/question/61054439