status
type
date
slug
summary
tags
category
icon
password
2471. Minimum Number of Operations to Sort a Binary Tree by Level
2nd approach deals with with cycle lengths. This approach is more Math. That one is related to the permutation group on
[0,1,..qz-1]. That one is based on the fact that each permutation is a series of cyclic transformations.A cyclic transformation can be denoted by (i0,i1,...,ik) which is fn fact i0→i1,i1→i2,⋯,ik−1→ik,ik→i0. A cyclic transformation of length k+1 can be performed by k 2-cycles(i.e. swaps).
The length's counting is using DFS.
For better understanding the permuation, let's consider the nodes on 2th level.
=>
The permutations are listed by the following
They can be represented by a cyclic transform
(0,2,3) which has length 3. This cyclic transform of length 3 can be proceeded by 2 swaps (2,3) then (0, 2) (order cannot be reversed, 2=|cycle|-1=3-1)#1718. Construct the Lexicographically Largest Valid Sequence
- Author:ran2323
- URL:https://www.blueif.me//article/16971a79-6e22-8089-9029-e3336fd2137f
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
