Leetcode记录「2」 | 湛蓝与蔚蓝

type

status

date

slug

summary

2471. Minimum Number of Operations to Sort a Binary Tree by Level

下面来自: https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/solutions/6175677/bfs-levelwise-transversal-compare-with-sorted-or-dfs-cycle-lengths-29-ms-beats-97-95

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)