Steward

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

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

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4296500.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>& preorder, vector<int>& inorder) {
        auto dfs = [&](
            this auto&& dfs,
            vector<int> &preorder,
            int pl,
            int pr,
            vector<int> &inorder,
            int il,
            int ir) -> TreeNode*
        {
            if (pl > pr || il > ir) {
                return NULL;
            }

            int i = 0;
            for (i = il; i <= ir; ++i) {
                if (preorder[pl] == inorder[i]) {
                    break;
                }
            }

            TreeNode *t = new TreeNode(preorder[pl]);
            t->left = dfs(preorder, pl + 1, pl + i - il, inorder, il, i - 1);
            t->right = dfs(preorder, pl + i - il + 1, pr, inorder, i + 1, ir);
            return t;
        };

        return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};