[数据结构与算法]2021-07-12 被代码暴揍的day4——剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

题目要求

代码实现

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int len = preorder.size();	//求出树的长度
        return build(preorder, inorder,0,len-1,0,len-1);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int f1,int f2,int s1,int s2)			
    //f1,f2;s1,s2分别代表是先序遍历的开头与结尾
    {
        int len = f2-f1+1;			//求出子树的长度
        if(len == 0) 
            return NULL;			//判断是否为空树
        TreeNode *head = new TreeNode(preorder[f1]);
        if(len == 1)
        {
            return head;			//判断是否为只有一个根节点
        }
        int index;
        for(int i=s1;i<=s2;i++)
        {
            if(inorder[i]==preorder[f1])
            {
                index = i-s1;		//分割树为左右子树并且建树
                break;
            }
        }
        head->left = build(preorder,inorder,f1+1,f1+index,s1,s1+index-1);
        head->right = build(preorder,inorder,f1+index+1,f2,s1+index+1,s2);
        return head;
    }
    
};