采用先序遍历的思想构建即可。

编码过程中,遇到了一个bug,只能通过25%的样例,反复检查逻辑问题,没有什么差错,最后面发现,原来是把第36行的==写成了=2333。总结:定位bug需要从多方面考虑:

  1. 如果是样例通过不了:考虑算法思路是否有误、运算符是不是写错了
  2. 如果是编译错误:考虑语法问题
  3. 如果是段错误、溢出:考虑边界问题,尤其是指针和数组下标
//
// 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;
    }
};