**Problem:**

Please find the problem here.

**Solution:**

This is basically asking for building a Cartesian tree, we will incrementally build it from left to right.

The base case is trivial, a Cartesian with a no node is null, a Cartesian tree with a single node is also trivial.

Given a Cartesian tree and then we wanted to add one node to it's right, how do we do it?

The first observation is that it has to be a right-most node, so the most obvious thing to do is to start with the current right-most node and see how we can patch the tree there.

If the value of the node we wanted to add to the tree is smaller than the current right-most value, we are lucky, we can simply add that as the right child of the current right-most node, and that's it, we get a new Cartesian tree!

If we are not so lucky, then what? We know that the new node must be higher up in the tree, so we go to the parent of the right-most node and try again, eventually we will go to the root and we will find one.

Once we find the right spot to put the new node in, the updating of the tree is easy.

**Analysis:**

The not-so-trivial fact is that this algorithm runs in linear time. The key observation is that once a node on the current right-most spine of the tree is less than a new node, it will never be on the right-most spine again. Therefore, we can account for the cost of comparison at node insertion time. That means the overall cost is $ O(n) $.

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/maximum-binary-tree #include "LEET_MAXIMUM_BINARY_TREE.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_MAXIMUM_BINARY_TREE { 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) { int n = nums.size(); if (n == 0) { return nullptr; } vector<int> parent; vector<TreeNode*> nodes; parent.resize(n); nodes.resize(n); parent[0] = -1; nodes[0] = new TreeNode(nums[0]); TreeNode* root = nodes[0]; for (int i = 1; i < n; i++) { nodes[i] = new TreeNode(nums[i]); nodes[i]->left = nullptr; nodes[i]->right = nullptr; int parent_candidate = i - 1; int child_candidate = -1; while (nums[i] > nums[parent_candidate]) { child_candidate = parent_candidate; parent_candidate = parent[parent_candidate]; if (parent_candidate == -1) { break; } } if (child_candidate != -1) { nodes[i]->left = nodes[child_candidate]; parent[child_candidate] = i; } parent[i] = parent_candidate; if (parent_candidate != -1) { nodes[parent_candidate]->right = nodes[i]; } else { root = nodes[i]; } } return root; } }; void Dump(TreeNode* node, int indent) { if (node != nullptr) { for (int i = 0; i < indent; i++) { cout << " "; } cout << node->val << endl; Dump(node->left, indent + 2); Dump(node->right, indent + 2); } } }; using namespace _LEET_MAXIMUM_BINARY_TREE; int LEET_MAXIMUM_BINARY_TREE() { Solution solution; int test1[] = { 3,2,1,6,0,5 }; TreeNode* answer = solution.constructMaximumBinaryTree(vector<int>(test1, test1 + _countof(test1))); Dump(answer, 0); return 0; }