（C++）数据结构——重建二叉树（根据前序遍历与中序遍历）

￡神魔★判官ぃ 2021-11-29 10:08 275阅读 0赞

> 对于二叉树来说，遍历方法有前序遍历、中序遍历、后序遍历，这三种遍历方法都是相对于根节点来说的。  
> 而我们已知一棵二叉树的中序遍历的前提下（必须已知），只要知道另外两种遍历方法的一种，我们就可以重构出这棵二叉树

这篇博客就通过一道剑指offer的一道题目来了解如何根据一棵二叉树的前序遍历与中序遍历重构这棵二叉树。不知道这两种遍历方法的请[点击这里][Link 1]。而主要的思想就是递归，不太懂递归的请[点击这里][Link 2]

### 题目描述 ###

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

### 题目解析 ###

首先解释为什么要用到递归，个人理解递归适合解决的问题类型为：该问题可以分成很多小问题，而这些小问题有着类似的解决方法。而二叉树的构建过程就是这样，一个二叉树可以看成是由很多小的二叉树组成，我们通过这些小的二叉树来构建出大的二叉树。  
再来解释如何使用已知的前序遍历与后序遍历构建二叉树，由它们的定义可知，前序遍历的第一个数就是二叉树的根节点，我们在中序遍历中找到这个数，在这个数的左边就是根节点左边的节点，根据这一部分点的数量，在前序遍历序列中往后推相同的数量，就可以得到左边子树的前序遍历序列，依此类推。根节点右边的节点也是如此。(如果看不懂的话，可直接看下面的代码）

### 源代码 ###

/**
     * 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* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        
            int len=vin.size();
            if(len==0)
                return NULL;
            int index;
            vector<int> left_pre,right_pre;
            vector<int> left_vin,right_vin;
            for(int i=0;i<len;++i)
            {
        
                if(vin[i]==pre[0])
                {
        
                    index=i;
                    break;
                }
            }
            for(int i=0;i<index;++i)
            {
        
                left_vin.push_back(vin[i]);
                left_pre.push_back(pre[i+1]);//注意下标
            }
            for(int i=index+1;i<len;++i)
            {
        
                right_vin.push_back(vin[i]);
                right_pre.push_back(pre[i]);//注意这里的下标
            }
            TreeNode* root=new TreeNode(pre[0]);
            root->left=reConstructBinaryTree(left_pre,left_vin);
            root->right=reConstructBinaryTree(right_pre,right_vin);
            return root;
        }
    };

[Link 1]: https://zhuanlan.zhihu.com/p/38603548
[Link 2]: https://zhuanlan.zhihu.com/p/59389994