319场周赛 逐层排序二叉树所需的最小操作数目
给你一个 值互不相同 的二叉树的根节点 root 。
在一步操作中,你可以选择 同一层 上任意两个节点,交换这两个节点的值。
返回每一层按 严格递增顺序 排序所需的最少操作数目。
节点的 层数 是该节点和根节点之间的路径的边数。
示例 1 :
输入:root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
输出:3
解释:
- 交换 4 和 3 。第 2 层变为 [3,4] 。
- 交换 7 和 5 。第 3 层变为 [5,6,8,7] 。
- 交换 8 和 7 。第 3 层变为 [5,6,7,8] 。
共计用了 3 步操作,所以返回 3 。
可以证明 3 是需要的最少操作数目。
示例 2 :
输入:root = [1,3,2,7,6,5,4]
输出:3
解释:
- 交换 3 和 2 。第 2 层变为 [2,3] 。
- 交换 7 和 4 。第 3 层变为 [4,6,5,7] 。
- 交换 6 和 5 。第 3 层变为 [4,5,6,7] 。
共计用了 3 步操作,所以返回 3 。
可以证明 3 是需要的最少操作数目。
示例 3 :
输入:root = [1,2,3,4,5,6]
输出:0
解释:每一层已经按递增顺序排序,所以返回 0 。
提示:
树中节点的数目在范围 [1, 105] 。
1 <= Node.val <= 105
树中的所有值 互不相同 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
本问题主要由两个部分组成:
- 遍历二叉树,找到每一层的子数组(层序遍历)
- 排序数组需要的最小交换次数(循环图)
第一次接触到循环图解决数组的最小交换次数。具体思路就是,假设原数组为 2 1 5 3 4,那么排序之后的数组就是1 2 3 4 5。尝试按照排序前后的位置建图,也就是排序后的位置指向其原位置,这样出度入度都是1。
排序后的第一个数1原位置为2,那么就有1 -> 2,排序后第二个数原位置为1,那么就有1 -> 2 ->1,这就是第一个循环图。第二个循环图是3 -> 4 -> 5 ->3。考虑两种情况,一个是交换两个循环图中的元素,比如2和3,3 1 5 2 4,那么循环图就是1 -> 2 -> 4 -> 5 -> 3 -> 1,可以看到两个循环图合并为一个循环图。假设交换同一个循环图中的元素,比如3和4,2 1 5 4 3。第二个循环图就会拆分为3 -> 5 -> 3, 4 -> 4,可以看到交换同一个循环图中的元素会将循环图拆分为两个循环图。
排序的目标就是使得最后有n个循环图,1->1,2->2.....n->n。所以要将所有节点数目大于1的循环图拆分为多个循环图,节点数目为K的循环图需要拆分K-1次,也就是交换K-1次。所以主要是求解所有的循环图并求和(其节点数目-1)。关键是具体如何实现求解循环图,由于是循环的,从i出发,我们可以记录其在原数组中的位置,并不断遍历下去,直到找到一个节点的原数组位置为i,也就是回来了并且是循环的,就结束。
code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void level_travel(TreeNode * root,vector<vector<int>> &nodes)
{
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
vector<int> level;
int len = q.size();
for(int i = 0;i < len;i ++)
{
TreeNode* cur = q.front();
q.pop();
level.push_back(cur -> val);
if(cur -> left != nullptr) q.push(cur -> left);
if(cur -> right != nullptr) q.push(cur -> right);
}
nodes.push_back(level);
}
}
int min_swap(vector<int> arr)
{
int n = arr.size();
pair<int,int> arrpos[n];
//for(int i = 0;i < n;i ++) cout<<arr[i]<<" "; cout<<endl;
//使用一个pair数组记录下每个元素的原位置
for(int i = 0;i < n;i ++)
{
arrpos[i].first = arr[i];
arrpos[i].second = i;
}
sort(arrpos,arrpos + n);
//记录当前节点是否已经在循环图中
vector<int> visited(n,0);
int ans = 0;
for(int i = 0;i < n;i ++)
{
//如果已经在循环图中并且本身就是循环图
if(visited[i] || arrpos[i].second == i) continue;
int cycle_size = 0;
int j = i;
while(!visited[j])
{
visited[j] = 1;
j = arrpos[j].second;
cycle_size++;
}
if(cycle_size > 0) ans += (cycle_size - 1);
}
return ans;
}
int minimumOperations(TreeNode* root) {
vector<vector<int>> nodes;
level_travel(root,nodes);
int ans = 0;
for(int i = 0;i < nodes.size();i ++)
ans += min_swap(nodes[i]);
return ans;
}
};
标签:周赛,319,TreeNode,int,循环,二叉树,排序,root,节点
From: https://www.cnblogs.com/huangxk23/p/16890043.html