题解 | #重建二叉树#

方法1：递归
例如，我们给定
前序遍历：1、2、3、4、5、6、7
中序遍历：3、2、4、1、6、5、7
我们知道，前序遍历的顺序是根，左子树，右子树，所以在一段前序遍历中，第一个一定是当前子树的根。我们找到这个根，然后我们知道中序遍历中，顺序是左子树，根，右子树。于是我们可以找到根的位置，其左边就是左子树，右边就是右子树，如此递归构造即可。接下来对于我们给定的例子来模拟构造一遍
先找根，找到左右子树的范围

然后在前序序列中把左子树，右子树的范围找出来

再继续对左子树找根，找到其左右子树的范围

依次类推，对每个子段都做类似操作即可





时间复杂度：每个节点都遍历了一遍，所以是O(n)
空间复杂度：存了一棵二叉树，所以是O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* remake(vector<int> pre, vector<int> vin) {
        if (pre.empty()) return NULL;//如果是当前序列为空，则返回空节点
        int root = pre[0];//找到当前子树的根
        TreeNode* node = new TreeNode(root);//创建新节点
        int position;//这个的意义是在中序遍历中找到根的位置，从而找到左右子树的范围
        for (int i = 0; i < vin.size(); i ++ ) {
            if (vin[i] == root) position = i;
        }
        vector<int> n_pre1(pre.begin() + 1, pre.begin() + position + 1);//左子树的前序遍历
        vector<int> n_pre2(pre.begin() + position + 1, pre.end());//右子树的前序遍历
        vector<int> n_vin1(vin.begin(), vin.begin() + position);//左子树的中序遍历
        vector<int> n_vin2(vin.begin() + position + 1, vin.end());//右子树的中序遍历
        node->left = remake(n_pre1, n_vin1);//递归构造左子树
        node->right = remake(n_pre2, n_vin2);//递归构造右子树
        return node;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return remake(pre, vin);
    }
};

方法2：非递归做法
非递归做法有点难理解
还是我们之前那个例子
前序遍历：1、2、3、4、5、6、7
中序遍历：3、2、4、1、6、5、7

前序遍历的第1个元素是1，是根节点，接下来根据中序遍历看2是它的左子树还是右子树
中序遍历第一个元素是3，不是根节点1，说明2是它的左子树根。接下来看3是其左子树还是右子树
中序遍历第一个元素是3，不是上一个的根节点2，说明3是其左子树。接下来看4
中序遍历第一个元素是3，是上一个的根节点3，所以4位于右子树。接下来看它位于哪个的右子树。从前序遍历看，4可能是1，2，3的右子树。从中序遍历看，最接近的是2，于是4是2的右子树。
同理便可以构造出这棵树来。
我们发现，找右子树的过程，也可以看做是将我们之前遍历过的前序遍历倒过来，然后看最后一个符合的地方是哪里，于是我们用栈来实现
时间复杂度：每个节点都遍历了一遍，所以是O(n)
空间复杂度：存了一棵二叉树和栈，所以是O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        stack<TreeNode* > sta;
        if (pre.empty()) return NULL;//特判一下空树
        int j = 0;//这是中序遍历的下标，判断左右子树用
        TreeNode* root = new TreeNode(pre[0]);//首先将根节点初始化好并加入到栈中
        sta.push(root);
        for (int i = 1; i < pre.size(); i ++ ) {
            if (sta.top()->val != vin[j]) {
                //如果栈顶和当前的中序遍历的第一个地方不同，说明是上一个的左节点
                TreeNode* node = new TreeNode(pre[i]);
                sta.top()->left = node;
                sta.push(node);
            } else {
                //如果相同，我们就开始从栈里找最后一个符合的位置，就是其右节点了
                TreeNode* node;
                while (!sta.empty() && sta.top()->val == vin[j]) {
                    j ++;
                    node = sta.top();
                    sta.pop();
                }
                TreeNode* tmp = new TreeNode(pre[i]);
                node->right = tmp;
                sta.push(tmp);
            }
        }
        return root;
    }
};