【剑指offer】5.根据前序和中序遍历重建二叉树

柔光的暖阳◎ 2023-06-20 09:05 42阅读 0赞

**题目描述：**  
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。  
前序： \{1, 2,4,7,3,5,6,8\}  
中序： \{4,7,2, 1, 5,3,8,6\}  
思路：我们知道，前序的第一个数字，是根节点，而中序遍历中，根节点左右分别是左子树和右子树。所以我们可以得知，重建一个最小的二叉树方法：  
前序\{1，2，3\}，  
中序\{2，1，3\}  
那么1 就是树的根节点，通过find（）函数找到中序中的1在位置1处，求出左边中序中的距离，作为间距distance：  
得出：中序中左子树距离区间：头head2和 head2+1+distance（因为find函数是前开后闭的区别）  
右子树的区间： head2+1+distance，到，end  
此时根据一开始找到的根节点1，来配置左右节点，由此来递归。  
终止条件是当head1和head2大于等于end即走到尾  
【注意】find 函数返回的是迭代器，用 auto 类型来定义（当你不知道类型时）

**代码实例：**

TreeNode* reConstructBinaryTree(vector<int>& preorder, vector<int>& inorder) { 
            return build(preorder, 0, preorder.size(), inorder,0, inorder.size());
        }
    private:
        TreeNode* build(vector<int>& preorder,int head1,int end1, vector<int>& inorder, int head2,int end2) { 
            if(head1>= end1 || head2>= end1)
                return NULL;
            
            int mid=preorder[head1];
            
            auto f=find(inorder.begin()+head2, inorder.begin()+end2, mid);      //因为find的区间是前闭后开的，所以++end2
            int distance=f-inorder.begin()-head2;     //得出左子树的节点的个数
            //-head2的原因是在求出中序的根节点后，左子树的head2，和右子树的head2是不同的
            TreeNode* root= new TreeNode(mid);  //已经构建好了左右节点为空，看上方struct TreeNode 结构体里面
            root->left=build( preorder, head1+1, head1+1+distance, inorder, head2, head2+distance);
            root->right= build( preorder, head1+1+distance, end1, inorder, head2+distance+1, end2);
            //掌握一个点：边界值find的参数前开后闭
            return root;        
        }

注意前闭后开区间，stl中很多迭代器都是这样的