题目

给定一个树的前序遍历和中序遍历, 输出二叉树.

Input: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]
output:
             3
            / \
           9   20
              /  \
            15    7

思路1

递归, 通过为子树截取新的遍历数组, 空间复杂度过大.

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.size() <= 0) return nullptr;
    TreeNode* root = nullptr;

    int val = preorder[0];
    if (root == nullptr) {
        root = new TreeNode(val);
    };

    vector<int>::iterator iter = find(inorder.begin(),inorder.end(), val);
    int n = 0;
    if (iter != inorder.end()){
      // 迭代器位置
       n = (int)distance(inorder.begin(),iter);
    }
    vector<int> leftInorder = vector<int>(inorder.begin(), inorder.begin() + n);
    vector<int> rightInorder = vector<int>(inorder.begin() + n + 1, inorder.end());
    vector<int> leftPreorder = vector<int>(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
    vector<int> rightPreorder = vector<int>(preorder.begin() + 1 + leftInorder.size(), preorder.end());

    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

思路2

递归, 计算出子节点的位置.

TreeNode* buildTreeRecrution (vector<int>& preorder, vector<int>& inorder, int left, int right, int &index) {
    if (index >= preorder.size()) return nullptr;

    while (left < right) {
        if (preorder[index] == inorder[left]) break;
        left++;
    }
    if (left >= right) return nullptr;

    TreeNode *root = new TreeNode(preorder[index++]);
    root->left = buildTreeRecrution(preorder, inorder, 0, left, index);
    root->right = buildTreeRecrution(preorder, inorder, left + 1, right ,index);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int index = 0;
    TreeNode* result = buildTreeRecrution(preorder, inorder, 0, (int)preorder.size(), index);
    return result;
}