首页 > 试题广场 >

魔力转圈圈

[编程题]魔力转圈圈
  • 热度指数:831 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

牛牛很喜欢玩二叉树。这天牛能送给了他一个以1为根结点的结点的二叉树,他想对这个二叉树进行一些加工。

牛牛刚刚学会转圈圈,所以很喜欢旋转。现在他想对这颗二叉树进行m次旋转。

每次旋转牛牛会指定一个结点,并让以这个结点为根的子树中的所有结点的左右儿子互换。

多次操作之后,牛牛希望以中序遍历的方式输出操作完之后的二叉树。
示例1

输入

5,3,[4,3,0,0,0],[2,0,0,5,0],[3,1,5]

输出

[2,3,1,5,4]

说明

最开始1的左儿子为4,右儿子为2
2的左儿子为3.
4的右儿子为5.
第一次操作结点3,结点3没有儿子,所以没有发生变化
第二次操作结点1,结点1的左儿子变为2,右儿子变为4. 
结点4的左儿子变为5,右儿子变为不存在。结点
结点2的左儿子变为不存在,右儿子变成3
第三次操作结点5,结点5没有儿子,不发生变化。
最开始1的左儿子为2,右儿子为4
2的右儿子为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;
}

发表于 2021-07-13 15:51:52 回复(0)
 直接操作的话会超时,case只能通过95%,利用偶数次旋转=没转,奇数次旋转=转一次的特点简化
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;
    }
};

思路:
 某一个节点
 a)被vector<int> k指名旋转,父节点旋转 = 不旋转
 b)被vector<int> k指名旋转,父节点不旋转 = 旋转
 c)没有被vector<int> k指名旋转,父节点旋转 = 旋转
 d)没有被vector<int> k指名旋转,父节点不旋转 = 不旋转
 那么怎么知道父节点转不转?
 参考vector<int> k和父节点的父节点。
 那么,只要从根开始依次判断就好了,因为根节点没有父节点,转不转只需要看vector<int> k。

发表于 2020-07-24 17:27:27 回复(0)
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;
    }
};

发表于 2020-07-14 03:24:57 回复(0)
function solve( n ,  m ,  l ,  r ,  k ) {
    // write code here
    var arr = []
    for(var i=0; i<m; i++) {
        change(k[i])
    }
    function change(x){
        r.splice(x-1 ,1 ,l.splice(x-1, 1, r[x-1])[0])
        if(l[x-1]!==0){
            change(l[x-1])
        }
        if(r[x-1]!==0){
            change(r[x-1])
        }
    }
    outPut(1)
function outPut(y) {
                    if(l[y-1]!==0){
                        outPut(l[y-1])
                    }
                        arr.push(y)
                                    console.log(111)
                        if(r[y-1]!==0) {
                            outPut(r[y-1])
                        }
                }
    return arr
}
module.exports = {
    solve : solve
};
发表于 2021-02-07 18:41:39 回复(0)

谁可以告诉我同样的写法java为什么过不了,是我哪里搞错了吗,哭

图片说明
图片说明

发表于 2020-07-29 15:23:47 回复(0)
java 写真恶心,递归写法始终过不了,必须改成非递归写法
发表于 2020-06-04 11:15:16 回复(1)