采用先序遍历的思想构建即可。
编码过程中,遇到了一个bug,只能通过25%的样例,反复检查逻辑问题,没有什么差错,最后面发现,原来是把第36行的==
写成了=
2333。总结:定位bug需要从多方面考虑:
- 如果是样例通过不了:考虑算法思路是否有误、运算符是不是写错了
- 如果是编译错误:考虑语法问题
- 如果是段错误、溢出:考虑边界问题,尤其是指针和数组下标
// // Created by jt on 2020/8/21. // #include <vector> using namespace std; struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int val): val(val), left(0), right(0) {} }; class Solution { public: /** * * @param preorder int整型vector * @param inorder int整型vector * @return TreeNode类 */ TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // write code here int size = preorder.size(); return inOrder(preorder, 0, size - 1, inorder, 0, size -1); } TreeNode* inOrder(vector<int> &preorder, int pL, int pR, vector<int> &inorder, int iL, int iR) { if (pL > pR) return nullptr; TreeNode *root = new TreeNode(preorder[pL]); int mid = iL; for (; mid <= iR; ++mid) if (inorder[mid] == root->val) break; int sizeLeft = mid - iL; // 中左右 左中右 root->left = inOrder(preorder, pL+1, pL+sizeLeft, inorder, iL, mid-1); root->right = inOrder(preorder, pL+sizeLeft+1, pR, inorder, mid+1, iR); return root; } };