---
# System prepended metadata

title: 2471. Minimum Number of Operations to Sort a Binary Tree by Level
tags: [Leetcode, Level Order Traversal, Tree, Medium]

---

# 2471. Minimum Number of Operations to Sort a Binary Tree by Level
###### tags: `Leetcode` `Medium` `Tree` `Level Order Traversal`
Link: https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/description/
## 思路
层序遍历
对于每层而言 有两个list(```vals```, ```sorted```)分别存这层的所有element
然后sort ```sorted``` list
并用```map```记录每个element在```vals```的位置
如果同一个idx i ```vals[i]```的值不等于```sorted[i]```的值 那么我们需要把```sorted[i]```的值和```vals```的值在```vals``` list互换一下
并把原先vals[i]的值的位置在map里面更新
## Code
```java=
class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        int ans = 0;
        boolean[][] palindrome = new boolean[n][n];
        for(int i=0; i<n; i++) palindrome[i][i] = true;
        for(int len=2; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j = i+len-1;
                if(s.charAt(i)==s.charAt(j)){
                    palindrome[i][j] = (j-i==1)?true:palindrome[i+1][j-1];
                }
            }
        }
        int[] dp = new int[n];
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                if(palindrome[j][i] && i-j+1>=k){
                    dp[i] = Math.max(dp[i], (j==0?0:dp[j-1])+1);
                }
                else dp[i] = Math.max(dp[i], j==0?0:dp[j-1]);
            }
        }
        return dp[n-1];
    }
}
```