# C++ O(N) solution

• This solution is inspired by @votrubac
Here is his brilliant solution
https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map

The key idea is:

1. We scan numbers from left to right, build the tree one node by one step;
2. We use a stack to keep some (not all) tree nodes and ensure a decreasing order;
3. For each number, we keep pop the stack until empty or a bigger number; The bigger number (if exist, it will be still in stack) is current number's root, and the last popped number (if exist) is current number's right child (temporarily, this relationship may change in the future); Then we push current number into the stack.
``````/**
* 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) {
vector<TreeNode*> stk;
for (int i = 0; i < nums.size(); ++i)
{
TreeNode* cur = new TreeNode(nums[i]);
while (!stk.empty() && stk.back()->val < nums[i])
{
cur->left = stk.back();
stk.pop_back();
}
if (!stk.empty())
stk.back()->right = cur;
stk.push_back(cur);
}
return stk.front();
}
};
``````

This solution will be slightly faster than normal recursive solution.

Again, great thanks to @votrubac !!!

• nit: you can remove the variable l, and always assign cur->left with stk.back(), then you can make it a bit more concise

• @zqfan
I have fixed that, thanks!

• Brilliant solution. Here is the java version.

``````    public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode left = null;
for (int num: nums){
TreeNode cur = new TreeNode(num);
while (!lklist.isEmpty() && lklist.peekFirst().val < cur.val){
cur.left = lklist.pop();
}

if (!lklist.isEmpty()){
lklist.peekFirst().right = cur;
}
lklist.push(cur);
}

return lklist.peekLast();
}
``````

• You can avoid the emptiness checks if you use a sentinel.

``````TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode sentinel(INT_MAX);
vector<TreeNode*> stk = {&sentinel};
for (int num : nums) {
TreeNode* cur = new TreeNode(num);
while (stk.back()->val < num) {
cur->left = stk.back();
stk.pop_back();
}
stk.back()->right = cur;
stk.push_back(cur);
}
return stk[1];
}``````

• @ManuelP
Good idea, thanks!

• I have a similar recursive solution but I think the running time for both your solution and mine should be O(nlogn). Actually the whole process is nothing but making a max Heap, right?

``````    public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums == null || nums.length == 0) {
return null;
}
TreeNode root = new TreeNode(nums[0]);
for(int i = 1; i < nums.length; i++) {
root = insert(root, new TreeNode(nums[i]));
}
return root;
}

private TreeNode insert(TreeNode root, TreeNode node) {
if(root == null) {
return node;
}
if(node.val > root.val) {
node.left = root;
return node;
}
root.right = insert(root.right, node);
return root;
}
``````

• @cwleoo I'm not sure why you'd say this is similar to a max heap. As for the complexity it actually is O(n) because each element will get added and popped from the stack exactly once

• @Ellest Yes, you are right. Each element is added and (possibly) popped from the stack once. So it's O(N). Thank you for your explanation!
BTW, after review of my code and the stack version, I found my solution can grow up to O(n^2) in the worst case if the tree is skewed. But in the stack version, it don't need to trace back to root in each iteration (while my solution will return root every time), so it is guarenteed O(N) runtime.

• @cwleoo Yeah your solutions looks like it's performing a modified insertion sort (I say modified because it's really sorting partitions divided by sequential max values). I really like this stack implementation as it handles the logic required for this problem brilliantly.

• Hi, @Mrsuyi, for the following case

and the last popped number (if exist) is current number's right child

shouldn't the last popped number be the current number's left child?

• Hi, @hjy06, great code! Well, the following line is redundant.

``````TreeNode left = null;
``````

BTW, the following line

``````lklist.push(cur);
``````

may not be obvious for programmers in other languages, especially C++, whose `push` are pushing to the end while the `push` of `LinkedList` pushes to the beginning. The above line is actually the same to `lklist.addFirst(cur);`.

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