剑指offer

原题链接

• • 关于二叉树重构的思考
  • 第一种递归重构方式(前序+中序)的图文思路
  • C++代码实现

这类题目一般是给定二叉树的前序，后序遍历，又已知二叉树的中序遍历，求二叉树的结构

1.二叉树的前序遍历可以知道第一个数字是二叉树的根节点，如果在搭配二叉树的中序遍历。我们通过扫描二叉树可以求得二叉树的左子树有几个节点，右子树有几个节点。只有这样才可以递归下去重构二叉树

2.同理如果已知二叉树的后序遍历和中序遍历，二叉树的后序遍历最后一个节点是二叉树的根节点，扫描中序遍历也可以知道二叉树左右子树节点的个数

3.通过上面的分析可知：如果给二叉树的前序遍历和后序遍历是不能重构二叉树的，因为不能确定二叉树的左右节点的个数

由上图我们更能了解到，如果给定的是二叉树的前序和后序，不知道中序是不能重构二叉树的。

同理如果给定的是后序遍历，思路和上图一样，只不过每次根节点都在最后找，这里不在赘述了。

class Solution {
public:
    TreeNode*_reConstructBinaryTree(vectorpre,vectorvin)
    {
        if(pre.empty()||vin.empty())
        {
            return nullptr;
        }
        int rootDate=pre[0];//根节点的值为
        TreeNode*root=new TreeNode(rootDate);//创建新节点
        //只有一个元素时候返回
        if(pre.size()==1&&vin.size()==1&&pre[0]==vin[0])
        {
            return root;
        }
        //计算中序遍历的左树大小
        int leftCout=0;
        for(int i=0;i0)
        {//将左子树的前序，中序进行递归
            root->left=_reConstructBinaryTree(vector(pre.begin()+1,pre.begin()+leftCout+1), vector(vin.begin(),vin.begin()+leftCout));
        }
        if(rightCout>0)
        {
            root->right=_reConstructBinaryTree(vector(pre.begin()+leftCout+1,pre.end()), vector(vin.begin()+leftCout+1,vin.end()));
        }
        return root;
    }
    
    
    TreeNode* reConstructBinaryTree(vector pre,vector vin) {
        if(pre.empty()||vin.empty())
        {
            return nullptr;
        }
        else
        {
            return _reConstructBinaryTree(pre,vin);
        }
    }
};