• 题目难度：中等

  • 题目描述：

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。 图片说明

提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比

  • 数据范围：n ≤ 2000，节点的值 −10000 ≤ val ≤ 10000

  • 要求：空间复杂度 O(n)，时间复杂度 O(n)

  • 思路一：

时间复杂度：O(nlogn)；空间复杂度：O(n) 图片说明

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.size() < 1 || vin.size() < 1) return nullptr;
        int lenPre = pre.size(), lenVin = vin.size();
        // 1. FIND ROOT
        TreeNode* root = new TreeNode(pre[0]);
        // 2. DIVIDE TWO PART: LEFT AND RIGHT -- ACCORDING TO VIN 
        for (int i = 0; i < lenVin; ++i) {
            if (root->val == vin[i]) {
                // LEFT PART
                vector<int> leftPre(pre.begin()+1, pre.begin()+1+i);
                vector<int> leftVin(vin.begin(), vin.begin()+i);
                root->left = reConstructBinaryTree(leftPre, leftVin);

                // RIGHT PART
                vector<int> rightPre(pre.begin()+1+i, pre.end());
                vector<int> rightVin(pre.begin()+1+i, vin.end());
                root->right = reConstructBinaryTree(rightPre, rightVin);
            }
        }
        return root;
    }
}
既然有递归，就能用栈去递归

  • 思路二：栈

时间复杂度：O(n)；空间复杂度：O(n) 提交结果：答案正确 运行时间：3ms 占用内存：520KB

借图：

图片说明 😘😘😘 原文链接🔗

在前序遍历中相邻的两个数字必定是只有两种情况：要么前序后一个是前一个的左节点；要么前序后一个是前一个的右节点或者其祖先的右节点

中序遍历的第一个数字就是左子树的最左节点

图片说明

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int preLen = pre.size(), vinLen = vin.size();
        if (preLen < 1 || vinLen < 1) return nullptr;
        TreeNode* root = new TreeNode(pre[0]);
        TreeNode* cur = root;
        stack<TreeNode*> stk;
        for (int i = 1, j = 0; i < preLen; ++i) {
            if (cur->val != vin[j]) {
                cur->left = new TreeNode(pre[i]);
                stk.push(cur);
                cur = cur->left;
            } else {
                j++;
                // 两种情况：根节点的右子树，最左端节点的右子树
                while (!stk.empty() && stk.top()->val == vin[j]) {
                    cur = stk.top();
                    stk.pop();
                    j++;
                }
                // cur 已经找到根节点（插入到根节点的右子树） 或者 不满足条件（最左端节点的右子树）
                cur->right = new TreeNode(pre[i]);
                cur = cur->right;
            }
        }
        return root;
    }
}

😘😘😘😘😘😘😘