654. Maximum Binary Tree

Link: https://leetcode.com/problems/maximum-binary-tree/

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    /
     2  0
       \
        1

Note:

• The size of the given array will be in the range [1,1000].

---

題目翻譯:

給定一個沒有重複的整數數組。此陣列上的最大樹構建定義如下：

1. root 是數組中的最大數字。
2. 左子樹是從左側子陣列構造的最大樹數除以最大數量。
3. 右子樹是從右部分子陣列構造的最大樹數除以最大數量。

按給定數組構造最大樹，並輸出該樹的根節點。

程式思路:
準備一個 stack 容器，每一個新元素加入時檢查 stack 最上面的元素是否大於新元素，如果不是的話將其元素 pop 出來為 child。也就是新元素的左子樹會得到容器內的最大的元素(如果新元素值夠大的話)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode *> s;
        const auto up = [&](int x) {
            TreeNode *child = nullptr;
            while(!s.empty() && (s.top()->val <= x)) {
                s.top()->right = child;
                child = s.top();
                s.pop();
            }
            return child;
        };
        for(const auto x :nums) {
            const auto node = new TreeNode(x);
            node->left = up(x);
            s.push(node);
        }
        return up(numeric_limits<int>::max());
    }
};