Verify Preorder Sequence in Binary Search Tree
@三千世界 Thank you so much!! This one is really clear!
@yu23 Share my solution without using an explicit stack, we can use the input vector as the stack : )
Apart from stack of recursion, what is the space complexity here? I think it is average O(logn) and worst O(n). Since each recursion function's pivot and bigger will be kept until all sub-function are done. Correct me if I'm wrong.
can anyone tell me how to analyze the time complexity of this algorithm?
No one has replied
Amazing algorithm, unexpected but beautiful.
you can make use of the short circuit by
return helper(arr, first + 1, tmp - 1) && helper(arr, tmp, end); then on average you can save half time.
could you explain this code for us? not that easy to understand lol
your solution is not O(nlogn) in worst case. lets say, there's a tree that each inter node has only right child. Then the time complex will be O(n^2). Please correct if i am wrong.
Run this case[12,8,2,3,7,4,5,9,6]
You changed the input data which is passed by reference. I don't think it is a good idea.
This is not O(1) space, because space consumption is implicit in recursion. However, Divide Conquer solution is subtle! Good solution~~~~~~~~~~
It is not tail recursion, the space is lgn.
Disabled Categories are greyed out
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.