[数据结构与算法]构造唯一的二叉树

二叉树前序遍历、中序遍历、后序遍历特点

• 前序遍历：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]--特点1
• 中序遍历：[[左子树中序遍历结果]，根节点，[右子树中序遍历结果]]--特点2
• 后序遍历：[[左子树后序遍历结果]，[右子树后序遍历结果]，根节点]--特点3

?? 注：同一棵子树的后序、前序遍历和中序遍历的长度相同--特点4

?? 注：前序和后序不能唯一确定一颗二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。

106.从中序与后序遍历序列构造二叉树

思想：寻找中序与后序序列的分割点，递归实现左右子树的构造。

要点：

1. 中序遍历的分割点：依据特点3，寻找出根节点(尾)，分割出左中序、右中序
2. 后序遍历的分割点：依据特点4，寻找分割长度，分割出左后序、右后序
3. 重点：分割的规则----不变量的选择：左闭右开，还有左开又闭，还是左闭又闭

步骤及代码

 TreeNode* traversal(vector<int>& inorder,vector<int>& postorder)
    {
        //第一步：判断数组大小为零的话，说明是空节点
        if(postorder.size()==0) return NULL;
        //第二步：根据后序遍历特点，最后一个元素为根节点---选取根节点
        int rootValue=postorder[postorder.size()-1];
        TreeNode* rootNode=new TreeNode(rootValue);
        if(postorder.size()==1) return rootNode;
        //第三步--根据根节点寻找切割点--注意循环内delimiterindex不可重复初始化
        int delimiterIndex;
        for(delimiterIndex=0;delimiterIndex<inorder.size();delimiterIndex++)
        {
            if(inorder[delimiterIndex]==rootValue) break;
        }

        //第四步--切割中序数组--左、右中序数组--依据遍历的特点--注意不变量左闭右开 [   )
        vector<int> leftinorder(inorder.begin(), inorder.begin() + delimiterIndex);
        vector<int> rightinorder(inorder.begin()+delimiterIndex+1,inorder.end());
        //第五步--切割后序数组--左、右后序数组--依据同一棵子树的后序遍历和中序遍历的长度相同--左闭右开
        //舍弃末尾元素
        postorder.resize(postorder.size()-1);
        //切割
        vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());
        vector<int> rightpostoeder(postorder.begin()+leftinorder.size(),postorder.end());

        //递归左区间、右区间
        rootNode->left=traversal(leftinorder,leftpostorder);
        rootNode->right=traversal(rightinorder,rightpostoeder);
        return rootNode;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0 || postorder.size()==0) return NULL;
        return traversal(inorder,postorder);
    }

105.从中序与后序遍历序列构造二叉树

思想：寻找中序与后序序列的分割点，递归实现左右子树的构造。

要点：

1. 中序遍历的分割点：依据特点1，寻找出根节点(头)，分割出左中序、右中序
2. 前序遍历的分割点：依据特点4，寻找分割长度，分割出左前序、右前序
3. 重点：? 分割的规则----不变量的选择：左闭右开，还有左开又闭，还是左闭又闭

步骤及代码--优化：上述每层递归定定义了新的vector（就是数组），既耗时又耗空间

 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0 || inorder.size()==0) return NULL;
        return traversal(preorder,0,preorder.size(),inorder,0,inorder.size());
    }

    TreeNode* traversal(vector<int>& preorder,int preBegin,int preEnd, vector<int>& inorder,int inBegin,int inEnd)
    {
        //第一步：判断前序数组大小为零的话，说明是空节点
        if(preBegin==preEnd) return NULL;
         //第二步：根据前序遍历特点，最后一个元素为根节点---选取根节点
        int rootValue=preorder[preBegin];
        TreeNode* rootNode=new TreeNode(rootValue);
        if(preEnd-preBegin==1) return rootNode;
        //第三步--根据根节点寻找切割点--注意循环内delimiterindex不可重复初始化
        int delimiterindex;
        for(delimiterindex=0;delimiterindex<inorder.size();delimiterindex++)
        {
            if(inorder[delimiterindex]==rootValue) break;
        }
        //第四步--切割中序数组--左、右中序数组--依据遍历的特点--注意不变量左闭右开 [   )
        int leftInBegin=inBegin;
        int leftInEnd=delimiterindex;
        int rightInBegin=delimiterindex+1;
        int rightInEnd=inEnd;
        //第五步--切割后序数组--左、右后序数组--依据同一棵子树的后序遍历和中序遍历的长度相同--左闭右开
        //舍弃元素
        //分割
        int leftPreBegin=preBegin+1;
        int leftPreEnd=preBegin+1+delimiterindex-leftInBegin;
        int rightPreBegin=preBegin+1+delimiterindex-leftInBegin;
        int rightPreEnd=preEnd;
        //第六步--递归
        rootNode->left=traversal(preorder,leftPreBegin,leftPreEnd,inorder,leftInBegin,leftInEnd);
        rootNode->right=traversal(preorder,rightPreBegin,rightPreEnd,inorder,rightInBegin,rightInEnd);
        return rootNode;
    }