654. Maximum Binary Tree

題目網址：https://leetcode.cn/problems/maximum-binary-tree/

題意：給一不重複的的整數 array nums, 利用下面的演算法遞迴建構 Maximum BT：

• 創建一個 root, 其值為 nums 中最大值
• 用最大值左邊的 subarray 遞迴建構左子樹
• 用最大值右邊的 subarray 遞迴建構右子樹

返回 nums 建構的 Maximum BT。

Solution：

想法：利用 DFS

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(0, nums.size() - 1, nums);
    }

private:
    TreeNode* dfs(const int left, const int right, const vector<int>& nums){
        if (left > right) {
            return nullptr;
        }

        int maxIdx = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[maxIdx] < nums[i]) {
                maxIdx = i;
            }
        }

        auto root = new TreeNode(nums[maxIdx]);
        root->left = dfs(left, maxIdx - 1, nums);
        root->right = dfs(maxIdx + 1, right, nums);

        return root;
    }
};

• time：$O(n^2)$ ➔ for loop 被呼叫 n 次
  • best case：每次 $O(log(n))$, 每次取出 maxIdx 恰好將 array 切分成兩個長度一樣的 subarray
    e.g. [1,3,2] ➔ 取出 3, 得到兩個 subarray : [1] 和 [2]
  • worse case：每次 $O(n)$, 其中 nums 由小到大, 每次取出 maxIdx 都為最右邊的 idx, 導致其中一個 subarray 為 empty array
    e.g. [1,2,3] ➔ 取出 3, 得到兩個 subarray : [1,2] 和 []
• space：$O(n)$ ➔ 遞迴深度不超過 n