思路很容易想,但是能不能顺利写出代码来又是另外一回事。
一共提交了16次才成功,我的妈啊。。。
为了加快编码速度,防止出错,加点小总结:
TreeNode* inOrder(vector<int> &inorder, int inL, int inR, vector<int> &postorder, int pL, int pR)
比TreeNode* inOrder(vector<int> &inorder, vector<int> &postorder, int inL, int inR, int pL, int pR)
好- 使用闭区间比使用开区间好
- 时刻注意区间范围,不要老想着区间是
0~size-1
#include <vector> using namespace std; class Solution { public: /** * * @param inorder int整型vector * @param postorder int整型vector * @return TreeNode类 */ TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { // write code here int size = inorder.size(); if (size < 1) return nullptr; return inOrder(inorder, 0, size-1, postorder, 0, size-1); } TreeNode* inOrder(vector<int> &inorder, int inL, int inR, vector<int> &postorder, int pL, int pR){ if (inL > inR) return nullptr; TreeNode *root = new TreeNode(postorder[pR]); int mid = inL; for (; mid <= inR; ++mid) if (inorder[mid] == root->val) break; int leftSize = mid - inL; // 左中右 左右中 root->left = inOrder(inorder, inL, mid-1, postorder, pL, pL+leftSize-1); root->right = inOrder(inorder, mid+1, inR, postorder, pL+leftSize, pR-1); return root; } };