Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 106. Construct Binary Tree from Inorder and Postorder Traversal

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4296193.html

題目：


解答：

/**
 * 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        auto dfs = [&](
            this auto&& dfs,
            vector<int> &inorder,
            int il,
            int ir,
            vector<int> &postorder,
            int pl,
            int pr) -> TreeNode*
        {
            if (il > ir || pl > pr) {
                return NULL;
            }
 
            int i = 0;
            for (i = il; i < inorder.size(); ++i) {
                if (inorder[i] == postorder[pr]) {
                    break;
                }
            }
 
            TreeNode *t = new TreeNode(postorder[pr]);
            t->left = dfs(inorder, il, i - 1, postorder, pl, pl + i - il - 1);
            t->right = dfs(inorder, i + 1, ir, postorder, pl + i - il, pr - 1);
            return t;
        };
 
        return dfs(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
};