|
| 1 | +/** |
| 2 | + * 2471. Minimum Number of Operations to Sort a Binary Tree by Level |
| 3 | + * https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/ |
| 4 | + * Difficulty: Medium |
| 5 | + * |
| 6 | + * You are given the root of a binary tree with unique values. |
| 7 | + * |
| 8 | + * In one operation, you can choose any two nodes at the same level and swap their values. |
| 9 | + * |
| 10 | + * Return the minimum number of operations needed to make the values at each level sorted in a |
| 11 | + * strictly increasing order. |
| 12 | + * |
| 13 | + * The level of a node is the number of edges along the path between it and the root node. |
| 14 | + */ |
| 15 | + |
| 16 | +/** |
| 17 | + * Definition for a binary tree node. |
| 18 | + * function TreeNode(val, left, right) { |
| 19 | + * this.val = (val===undefined ? 0 : val) |
| 20 | + * this.left = (left===undefined ? null : left) |
| 21 | + * this.right = (right===undefined ? null : right) |
| 22 | + * } |
| 23 | + */ |
| 24 | +/** |
| 25 | + *@param {TreeNode} root |
| 26 | + *@return {number} |
| 27 | + */ |
| 28 | +varminimumOperations=function(root){ |
| 29 | +letresult=0; |
| 30 | +constqueue=[root]; |
| 31 | +constlevelValues=[]; |
| 32 | + |
| 33 | +while(queue.length){ |
| 34 | +constlevelSize=queue.length; |
| 35 | +constvalues=[]; |
| 36 | + |
| 37 | +for(leti=0;i<levelSize;i++){ |
| 38 | +constnode=queue.shift(); |
| 39 | +values.push(node.val); |
| 40 | +if(node.left)queue.push(node.left); |
| 41 | +if(node.right)queue.push(node.right); |
| 42 | +} |
| 43 | + |
| 44 | +levelValues.push(values); |
| 45 | +} |
| 46 | + |
| 47 | +for(constvaluesoflevelValues){ |
| 48 | +constsorted=[...values].sort((a,b)=>a-b); |
| 49 | +constindexMap=newMap(values.map((val,i)=>[val,i])); |
| 50 | +letswaps=0; |
| 51 | + |
| 52 | +for(leti=0;i<values.length;i++){ |
| 53 | +if(values[i]!==sorted[i]){ |
| 54 | +consttargetIndex=indexMap.get(sorted[i]); |
| 55 | +[values[i],values[targetIndex]]=[values[targetIndex],values[i]]; |
| 56 | +indexMap.set(values[targetIndex],targetIndex); |
| 57 | +indexMap.set(values[i],i); |
| 58 | +swaps++; |
| 59 | +} |
| 60 | +} |
| 61 | + |
| 62 | +result+=swaps; |
| 63 | +} |
| 64 | + |
| 65 | +returnresult; |
| 66 | +}; |