题目描述

重建二叉树

思路

递归的思路很简单，要构建好整棵二叉树，就得先构建好左右子树，而要构建以左右子结点为根节点的子二叉树，又要分别构建好相应的子树。

题目给定的buildTree函数不适合用于递归，因为仅仅传入两个vector参数不能操作子树，为了实现递归，得自己再创建一个函数来实现相应的功能。这里使用helper，传入的是两个vector和子树相对于preorder和inorder的索引上下限，这里传进去的上下限就相当于两棵子树，一开始我还担心每一次递归传进去vector会造成内存的浪费，但是意识到传进去的是引用，大家都是共用一段内存空间，所以多虑了。

需要熟练使用递归还得多加练习递归算法，二叉树的很多算法题目都可以使用递归来解决。递归首先考虑宏观的操作，本题中宏观操作为：
root->left = helper();root->right = helper();
然后考虑边界值：
传进去的任意子树索引中，开始索引>结束索引时，返回空。

然后即可将精力放在开始索引和结束索引上了。

其实自己在动手实现的过程中，配合使用preorder和inorder的时候，发现找到根节点比较容易，但是为了传进去子树的索引上下限，需要确定子树的长度，确定子树的长度就需要定位根节点在inorder中的索引值，而且这一操作非常频繁，为了减少查找的时间复杂度，可以使用unordered_map来将时间复杂度降为$O(1)$，而花费额外的空间来存放结点值->索引值的映射关系是值得的。

样例

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // cout << preorder.size();
        // 将中序遍历（值，索引）存放在哈希表中
        for(int i = 0;i<inorder.size();i++){
            mp[inorder[i]] = i;
        }
        return helper(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pleft, int pright, int ileft, int iright){
        if(pleft>pright) return nullptr;

        TreeNode* root = new TreeNode(preorder[pleft]);

        int in_root_index = mp[preorder[pleft]]; // 根节点在inorder中的索引
        int left_len = in_root_index - ileft;  // 左子树的长度
        int right_len=iright - in_root_index;  // 右子树的长度
        // cout << in_root_index << left_len << ' ' << right_len<< endl;

        root->left = helper(preorder, inorder, pleft+1, pleft+left_len, ileft, in_root_index-1);
        root->right = helper(preorder, inorder, pleft+left_len+1, pright, in_root_index+1, in_root_index+right_len);
        return root;
    }
};