I havent coded it but this is what I think:
In order traversal the tree, put tree node in a list. Then swap the one bigger than its successor and the one smaller than its predecessor
Thanks, but I have a problem. For example 1 2 3 4 5 -> 1 4 3 2 5. The 2 and the 4 are swapped. However, 4, 5 are bigger than their predecessor, and 1, 2 are smaller than their successor. How do I know which two should be swapped.
In a sorted array of distinct elements:
A B C D E F G
If we swap B and F then we have:
A F C D E B G
We can see that the array is in ascending order until F and C, we record this and continue from C.
then at E and B we see the order if wrong again.
So we need to swap F (it is bigger so it comes from a later position) and B (it is smaller so it comes from a earlier position).
There is a special case when we swap two neighbouring elements:
where we will only detect the broken order once.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.