牛牛很喜欢玩二叉树。这天牛能送给了他一个以1为根结点的个结点的二叉树,他想对这个二叉树进行一些加工。
牛牛刚刚学会转圈圈,所以很喜欢旋转。现在他想对这颗二叉树进行m次旋转。
每次旋转牛牛会指定一个结点,并让以这个结点为根的子树中的所有结点的左右儿子互换。
多次操作之后,牛牛希望以中序遍历的方式输出操作完之后的二叉树。
牛牛很喜欢玩二叉树。这天牛能送给了他一个以1为根结点的个结点的二叉树,他想对这个二叉树进行一些加工。
牛牛刚刚学会转圈圈,所以很喜欢旋转。现在他想对这颗二叉树进行m次旋转。
每次旋转牛牛会指定一个结点,并让以这个结点为根的子树中的所有结点的左右儿子互换。
5,3,[4,3,0,0,0],[2,0,0,5,0],[3,1,5]
[2,3,1,5,4]
最开始1的左儿子为4,右儿子为22的左儿子为3.4的右儿子为5.第一次操作结点3,结点3没有儿子,所以没有发生变化第二次操作结点1,结点1的左儿子变为2,右儿子变为4.结点4的左儿子变为5,右儿子变为不存在。结点结点2的左儿子变为不存在,右儿子变成3第三次操作结点5,结点5没有儿子,不发生变化。最开始1的左儿子为2,右儿子为42的右儿子为3.4的左儿子为5.中序遍历结果为[2,3,1,5,4]
数据保证结点1为根节点第一个参数n代表树的结点个数第二个参数m代表需要进行的操作个数第三个参数l包含n个元素,代表每个结点的左儿子结点。如果为0则代表该点无左儿子第三个参数r包含n个元素,代表每个结点的右儿子结点。如果为0则代表该点无右儿子第四个参数k包含m个元素,代表m次操作的结点编号。
// “自顶而下” 递归地翻转每一颗子树 void invertTree(struct TreeNode* root) { if (!root) return; struct TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; invertTree(root->left); invertTree(root->right); } struct TreeNode* buildTree(struct TreeNode** repos, int* l, int* r, int root_id) { // recursion exit condition if (!root_id) return NULL; struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode)); if (!root) { fputs("buildTree memory overflow: Failed to allocate the memory!", stderr); return NULL; } root->val = root_id; root->left = buildTree(repos, l, r, *(l - 1 + root_id)); root->right = buildTree(repos, l, r, *(r - 1 + root_id)); return *(repos + root_id) = root; } void inorderTraversal(struct TreeNode* root, int* ans, int* ansSize) { if (!root) return; inorderTraversal(root->left, ans, ansSize); *(ans + (*ansSize)++) = root->val; inorderTraversal(root->right, ans, ansSize); } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 魔力转圈圈 * @param n int整型 * @param m int整型 * @param l int整型一维数组 * @param lLen int l数组长度 * @param r int整型一维数组 * @param rLen int r数组长度 * @param k int整型一维数组 * @param kLen int k数组长度 * @return int整型一维数组 * @return int* returnSize 返回数组行数 */ int* solve(int n, int m, int* l, int lLen, int* r, int rLen, int* k, int kLen, int* returnSize ) { *returnSize = 0; int* ans = (int*) malloc(n * sizeof(int)); if (!ans) { fputs("solve memory overflow: Failed to allocate the memory!", stderr); return NULL; } struct TreeNode* repos[n]; // 节点仓库 struct TreeNode* root = buildTree(repos, l, r, 1); int i; for (i = 0; i < m; ++i) invertTree(*(repos + *(k + i))); inorderTraversal(root, ans, returnSize); return ans; }
class Solution { public: vector<int> res; void rotate(int root,vector<int>& l, vector<int>& r, vector<bool>& flag){ if(flag[root]){ swap(l[root],r[root]); if(l[root]) flag[l[root]-1]=!flag[l[root]-1]; if(r[root]) flag[r[root]-1]=!flag[r[root]-1]; } if(l[root]) rotate(l[root]-1,l,r,flag); if(r[root]) rotate(r[root]-1,l,r,flag); } void dfs(vector<int>& l, vector<int>& r,int i){ if(l[i]!=0) dfs(l,r,l[i]-1); res.push_back(i+1); if(r[i]!=0) dfs(l,r,r[i]-1); } vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) { // write code here vector<bool> flag(n,false); for(auto&c:k) flag[c-1]=!flag[c-1]; //从根节点开始!! rotate(0,l,r,flag); //中序遍历输 dfs(l,r,0); return res; } };
class Solution { public: /** * 魔力转圈圈 * @param n int整型 * @param m int整型 * @param l int整型vector * @param r int整型vector * @param k int整型vector * @return int整型vector */ vector<int> v; void rotate(int t, vector<int> &l, vector<int> &r, int *cnt){ if(cnt[t]&1){ swap(l[t-1], r[t-1]); cnt[l[t-1]]++; cnt[r[t-1]]++; } if(l[t-1]!=0) rotate(l[t-1], l, r, cnt); if(r[t-1]!=0) rotate(r[t-1], l, r, cnt); return; } void inOrder(int t, vector<int> &l, vector<int> &r){ if(l[t-1]!=0) inOrder(l[t-1], l, r); v.push_back(t); if(r[t-1]!=0) inOrder(r[t-1], l, r); return; } vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) { int cnt[n+1]; memset(cnt, 0, sizeof(cnt)); for(auto &x: k) cnt[x]++; rotate(1, l, r, cnt); inOrder(1, l, r); return v; } };