[数据结构与算法]剑指offer J27 重建二叉树

题目描述

给定节点数为 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)

输出示例1:

输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

示例2:

输入：[1],[1] 返回值：{1}

示例3:

输入： [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值： {1,2,5,3,4,6,7}

解题思路

这里我们先解释一下树的三种遍历方式，前序遍历是从根节点开始,以根-左-右的顺序递归遍历树,中序遍历的顺序是左-根-右，后序遍历的顺序则是左-右-根。因此前序遍历数组的第一项一定是树根,以pre数组 [1,2,4,7,3,5,6,8]为例,可以确定树根节点的值为1。然后我们在vin数组中[4,7,2,1,5,3,8,6] 找到1，我们按照1的位置，很明显,1左边的数组位于左儿子节点(及以下),1右边的数组位于右儿子节点(及以下),将vin数组分为vin1[4,7,2]和vin2[5,3,8,6],然后反过来分解pre数组，可分为pre1[2,4,7]和pre2[3,5,6,8],如下图:

然后只要递归分解数组就行了。

参考代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:  
   //待构建的树的头部
    TreeNode* HEAD;
    //确定根节点，分解pre和vin
    void subArry(vector<int> pre,vector<int> vin,TreeNode* treeLocation){
       //pre的size为1，不需要分解，直接return
        if(pre.size()==1){
            return;
        }
        //子pre数组
        vector<int> newPre;
        //子vin数组
        vector<int> newVin;
        //确定树左边的pre和vin
        int k1=1,k2=0;
        while(vin[k2]!=pre[0]){
            newPre.push_back(pre[k1]);
            newVin.push_back(vin[k2]);
            k1++;k2++;
        }
        if(!newPre.empty()) {
        //pre第一项为当前根节点值
            treeLocation->left=new TreeNode(newPre[0]);
            //左边继续分解
            subArry(newPre, newVin,treeLocation->left);
        }
        //确定树右边的pre和vin
        k2++;
        newPre.clear();
        newVin.clear();
        while(k1<pre.size()&&k2<vin.size()){
            newPre.push_back(pre[k1]);
             newVin.push_back(vin[k2]);
            k1++;k2++;
        }
        if(!newPre.empty()) {
        //pre第一项为当前根节点值
            treeLocation->right=new TreeNode(newPre[0]);
            //右边继续分解
            subArry(newPre, newVin,treeLocation->right);
        }
    }
    
    //方法入口
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
       if(!pre.empty()){//当pre为空直接跳过递归,返回HEAD(HEAD为null)
       //pre第一项为当前根节点值
        HEAD=new TreeNode(pre[0]);
        subArry(pre,vin,HEAD);
       }    
           return HEAD;
     
    }
};