【代码随想录day 16】 力扣 106.从中序与后序遍历序列构造二叉树

视频讲解：https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
力扣题目：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

通过中序遍历与后续遍历来构造二叉树要注意的是

1. 先确定根节点，也就是后序遍历的最后一个元素
2. 根据根节点的值将中序遍历分为左中序和右中序，左中序就是左子树，右中序就是右子树。
3. 根据左中序的长度可以在后序遍历中找到左后序的长度，同时得到右后序的长度，在其找出根节点，循环切割中序遍历和后序遍历
4. 当切割的数组长度为1时就是最后一个根节点了，也就是遍历到了叶子节点，返回root
5. 如果便利的数组长度为0，则证明是空树，直接返回空即可。

class Solution {
public:
TreeNode *traversal(vector<int>&inorder,vector<int>&postorder)
{
            //如果遍历数组长度为0，则为空树
        if(postorder.size()==0) return NULL;

        //找到后序遍历最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size()-1];
        TreeNode *root = new TreeNode(rootValue);

        //叶子节点
        if(postorder.size() == 1) return root;

        //找切割点
        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舍弃末尾元素
        postorder.resize(postorder.size()-1);

        //切割后序数组  左后序  右后序
        vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
        vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());

        //开始递归
        root->left=traversal(leftInorder,leftPostorder);
        root->right=traversal(rightInorder,rightPostorder);

        //返回值
        return root;
}
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //如果两数组都为空，则树为空
        if(inorder.size()==0 &&postorder.size()==0) return NULL;

        return traversal(inorder,postorder);

    }
};