力扣105. 从前序与中序遍历序列构造二叉树

Problem: 105. 从前序与中序遍历序列构造二叉树

题目描述

思路

首先明确：

1.前序遍历的顺序是根-左-右（即先遍历根节点，再左子树，再右子树）
2.中序遍历的顺序是左-右-根

1.前序遍历数组中的第一个元素一定是树的根节点
2.每次在前序数组中找出根节点，再到的中序数组中找出根节点，则在中序数组中该根节点的左侧为根节点的左子树、右侧是根节点的右子树（则我们每次要重复该操作去构造二叉树）

解题方法

1.定义构造二叉树的递归函数TreeNode* build(vector& preorder, int preStart, int preEnd, vector& inorder, int inStart, int inEnd)其中preStart是每次递归前序遍历数组中的起始位置preEnd是每次递归前序遍历数组中的结束位置，同理inStart 每次递归中序遍历数组的起始位置inEnd每次递归数组的结束位置
2.定义一个unordered_map<int, int>valToIndex;在中序遍历数组中每次根节点的索引位置
3.每次递归中先在先序数组中取出当前的父节点再再中序数组中找出当前父节点的索引（index），通过计算得到左子树所有节点的长度：int leftSize = index - inStart;
4.下一次递归的起始与结束位置为preStart + 1, preStart + leftSize,inStart, index - 1,preStart + leftSize + 1，index + 1, inEnd

复杂度

时间复杂度:

$O(n)$；其中$n$为树节点的个数

空间复杂度:

$O(heigh)$；其中$height$为树的高度

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    //Recode the element of inorder array into the unorderd_map<int, int>
    unordered_map<int, int>valToIndex;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
        //Base case
        if (preStart > preEnd) {
            return nullptr;
        }
        //The first element in preorder array is the root of binary tree that
        //we shoud creat
        int rootVal = preorder[preStart];
        //Find the index of rootVal in inorder array
        int index = valToIndex[rootVal];
        //Calculate the size of left tree
        int leftSize = index - inStart;

        //Create the root firstly
        TreeNode* root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        root -> left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
        root -> right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
        return root;
    }
};