[Lc]105从前序与中序遍历序列构造二叉树

题解

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

递归，先序的首字母是根节点，而中序的根节点区分左右子树，利用这个性质递归

• 时间复杂度$O(n)$,分析见官方题解
• 空间复杂度$O(n)$，存储整课树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,0, preorder.size()-1, inorder, 0, inorder.size()-1);
        //调用建立树的递归函数
    }
    TreeNode* build(vector<int>& preorder,int pLeft,int pRight,vector<int>& inorder,int iLeft,int iRight){//建立树的递归函数
        if(pLeft>pRight || iLeft>iRight) return NULL;
        //若数组为空或递归过程中出现左右子树边界倒挂，则直接返回空数组
        TreeNode *root = new TreeNode(preorder[pLeft]);
        //先序遍历的第一个数是根节点，因此建立新树，根节点为preorder[pLeft]
        int i = iLeft;
        while(i<=iRight && preorder[pLeft]!=inorder[i]) i++;
        //这两步找根节点在在中序遍历数组中的位置，该位置左右分别是左右子树
        int lLength = i - iLeft;
        int rLength = iRight - i;//计算左右子树的数组长度
        root->left = build(preorder,pLeft+1,pLeft+lLength,inorder,iLeft,iLeft+lLength-1);//递归生成左子树，其中先序数组是去掉第一个数（根节点）到由中序遍历确定的中间位置（该位置左右是左右子树）；中序数组是从第一个数到中间（即左子树）,最后一个参数-1去掉根节点
        root->right = build(preorder,pLeft+lLength+1,pRight,inorder,iLeft+lLength+1,iRight);//递归生成右子树，其中先序数组和中序数组分别是两个数组的右子树。
        return root;
    }
};