might be better to include some explanation as the implementation is a bit abstract.
traverse the array once and create the node one by one. and use stack to store a decreasing sequence.
each step, we create a new curNode. compare to the peek of stack,
2.a. keep popping the stack while (stack.peek().val < curNode.val), and set the last popping node to be curNode.left.
Because the last one fulfilling the criteria is the largest number among curNode's left children. => curNode.left = last pop node
2.b. after popping up all nodes that fulfill (stack.peek().val < curNode.val),
thus (stack.peek().val > curNode.val), the stack.peek() is curNode's root => peek.right = curNode
return the bottom node of stack.
Hi, @votrubac, could you please explain what you mean by
The current number becomes a leaf of the right subtree.
Isn't the current number the root of the right subtree?
Tried to re-read the description again, and I agree the wording is a bit confusing (will post a picture to clarify).The current number "breaks" the right subtree into two parts; it becomes the leaf of the first part, and the second part becomes it's left subtree.