[数据结构与算法]LeetCode106-从中序与后序遍历序列构造二叉树-树-数据结构-分治

原题链接

Note：

跟105前序和中序还原二叉树一样，不过给的后序遍历，每次要创建出来的子树根节点变成从后序数组的后面往前找就好了

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int last = 0;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        last = postorder.size() - 1;
        int p = 0;
        for(int i = 0; i < inorder.size(); i ++)
            if(inorder[i] == postorder[last]){
                p = i;
                break;
            }
        auto root = new TreeNode(postorder[last]);
        last --;
        root -> right = dfs(inorder, postorder, p + 1, postorder.size() - 1, last --);
        root -> left = dfs(inorder, postorder, 0, p - 1, last --);

        return root;
    }

    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int l, int r, int p){
        if(l > r){
            last ++;
            return NULL;
        }
        auto root = new TreeNode(postorder[p]);
        int k = 0;
        for(int i = 0; i < inorder.size(); i ++)
            if(inorder[i] == postorder[p]){
                k = i;
                break;
            }
                
        root -> right = dfs(inorder, postorder, k + 1, r, last --);
        root -> left = dfs(inorder, postorder, l, k - 1, last --);
        
        return root;
    }
};