算法：利用前序序列和中序序列构造二叉树

题目

链接：leetcode链接

思路分析

前序遍历的顺序是：根 + 左子树 + 右子树
中序遍历的顺序是： 左子树 + 根 + 右子树

所以，我们可以通过前序遍历获得二叉树的根
可以通过中序遍历去分割二叉树，将二叉树分割成 左子树 根 右子树
然后递归操作即可。

遍历前序序列，前序序列中的每一个元素都是一颗子树的根节点

所以，我们需要一个变量i来遍历前序序列，注意，在递归中，我们需要引用或者指针来传递该参数

找到根节点之后，在中序遍历中去寻找这个根节点，就可以将中序遍历分成三段了。

然后递归调用即可。

注意：有一点比较坑，就是如何去处理空树，当我们要分割后的区间的长度为0的时候就是空树，在具体代码中，我们采用了区间的起始下标和结尾下标
当 起始下标 > 结尾下标 的时候，就出现了空树，返回nullptr即可

代码

TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend)
    {
        if(inbegin > inend)
        return nullptr;
        TreeNode* root = new TreeNode(preorder[prei]);

        int begin = inbegin,end = inend;
        int rooti = 0;

        while(begin <= end)
        {
            if(inorder[begin] == root->val)
            {
            rooti = begin;
            break;
            }
            begin++;
        }

        prei++;

        root->left = build(preorder,inorder,prei,inbegin,rooti-1);
        root->right = build(preorder,inorder,prei,rooti+1,inend);

        return root;
    }


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return build(preorder,inorder,i,0,inorder.size() - 1);
    }

变式题

题目：利用中序序列和后序序列构造二叉树

链接：leetcode链接

思路分析

和上面一样，思路大致相同

后序遍历找根（根在后面）
中序遍历分割子树

后序遍历的顺序是 左子树 + 右子树 + 根

与上面不同的是，

1. 我们需要从后向前遍历后序遍历，i需要一直–
2. 我们在构建好根节点之后，我们需要接着构造右子树，而并非左子树。

其余与上面几乎相同

代码

TreeNode* build(vector<int>& inorder,vector<int>& postorder,int& posti,int inbegin,int inend)
    {
        if(inbegin > inend)
        return nullptr;

        TreeNode* root = new TreeNode(postorder[posti]);//后序遍历找根

        int begin = inbegin,end = inend;
        int rooti = 0;

        while(begin <= end)//中序遍历分割
        {
            if(inorder[begin] == root->val)
            {
                rooti = begin;
            }

            begin++;
        }

        if(begin > end)
        {
            cout << "很抱歉，中序序列和后序序列不匹配" << endl;
            exit(1);
        }
        posti--;

        root->right = build(inorder,postorder,posti,rooti+1,inend);
        root->left = build(inorder,postorder,posti,inbegin,rooti-1);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return build(inorder,postorder,i,0,inorder.size() - 1);
    }