C++ Divide-and-Conquer Solution


  • 0
    G
    class Solution {
    private:
        TreeNode* merge_trees(TreeNode* lt, TreeNode* rt) {
            if (lt == nullptr) return rt;
            if (rt == nullptr) return lt;
            if (lt->val < rt->val) {
                rt->left = merge_trees(lt, rt->left);
                return rt;
            } else {
                lt->right = merge_trees(lt->right, rt);
                return lt;
            }
        }
        TreeNode* partition(vector<int>& nums, int s, int e) {
            if (s >= e) return nullptr;
            if (s + 1 == e) return new TreeNode(nums[s]);
            int m = s + (e - s) / 2;
            TreeNode* lt = partition(nums, s, m), * rt = partition(nums, m, e);
            return merge_trees(lt, rt);
        }
    public:
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            return partition(nums, 0, (int)nums.size());
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.