Steward

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

程式語言 - LeetCode - C++ - 654. Maximum Binary Tree

---

題目：


解答：

/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();

        auto dfs = [&](this auto&& dfs, int l, int r) -> TreeNode* {
            if (l > r) {
                return nullptr;
            }

            int idx = l;

            for (int i = l; i <= r; ++i) {
                if (nums[i] > nums[idx]) {
                    idx = i;
                }
            }

            TreeNode *n = new TreeNode(nums[idx]);

            n->left = dfs(l, idx - 1);
            n->right = dfs(idx + 1, r);

            return n;
        };

        return dfs(0, n-1);
    }
};