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

Leetcode link

题目简介

本题给了我们一棵二叉树，并且保证了每个节点都是唯一的

题目要求我们针对每一层对这个树做升序排序，然后返回在排序中所需的最少交换次数

解题思路

首先，针对每一层的遍历，我们优先选用 bfs 来求解

有了 bfs 我们可以很快得到每一层的所有节点，并且我们可以将其升序排序

题目的难点在于要怎么获取最少的交换次数呢？

我们可以遍历当前层的节点，通过不断把排序好的值与排序前的位置当前值进行交换，并将交换的次数记录下来，这样等到最后还原成原来的值之后，所得到的次数就是最少的次数

我们可以借用一个 map 来保存当前层所有节点的值与原来的位置（下标）的映射

有了这个映射之后，我们只需要遍历当前层，然后对比排序前后，如果不一致，从 map 中获取排序后的值原来的位置，然后做三件事：

1. 交换新位置与原来的位置的值
2. 更新 map
3. 计算次数

然后不断循环对比就好

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minimumOperations = function (root) {
    if (!root) return 0

    let count = 0
    const queue = [root]

    while (queue.length > 0) {
        const len = queue.length
        const curLevel = []

        // bfs
        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            curLevel.push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }

        // sort
        const sortedLevel = [...curLevel].sort((a, b)=>a-b)

        // count the operations
        const map = new Map()
        for (let i = 0; i < curLevel.length; i++) {
            map.set(curLevel[i], i)
        }

        for (let i = 0; i < curLevel.length; i++) {
            while (curLevel[i] !== sortedLevel[i]) {
                // get the original position of sorted node
                const originalIdx = map.get(sortedLevel[i])

                // swap
                map.set(curLevel[i], originalIdx)
                const temp = curLevel[originalIdx]
                curLevel[originalIdx] = curLevel[i]
                curLevel[i] = temp

                // add 1 operation
                count++
            }
        }
    }

    return count
};