首页 > 试题广场 >

循环右移二叉树

[编程题]循环右移二叉树
  • 热度指数：2019 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现有一棵个节点构成的二叉树，请你将每一层的节点向右循环位移位。某层向右位移一位(即)的含义为：
1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。
2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了，则会变成双亲节点同级的最左边的节点的左孩子节点)
3.该层的每一个节点同时进行一次位移。
4.是从最下面的层开始位移，位移完每一层之后，再向上，直到根节点，位移完毕。

如果从最后一层开始对该二叉树的每一层循环位移位。以下方二叉树为例，： 

      1
     / \
    2   3
       / \
      4   5
位移最后一层，5变成2的左孩子节点，4变成3的右孩子节点，如下图: 
      1
     / \
    2   3
   /     \
  5       4
再位移倒数第二层，3变成1的左孩子节点，2变成1的右孩子的节点，它们的孩子节点随着一起位移，如下图： 
      1
     / \
    3   2
    \   /
     4 5
根节点没有双亲节点，不用位移，位移完毕

现在给你这棵二叉树，请你返回循环右移位后的二叉树。
示例1

输入

{1,2,3,#,#,4,5},1

输出

{1,3,2,#,4,5}

说明

解释见题面描述。
示例2

输入

{1,2,3,4},2

输出

{1,2,3,#,#,4}

说明

      1
     / \
    2   3
   /
  4




变为





      1
     / \
    2   3
       /
      4
示例3

输入

{1,#,3,4,5},1

输出

{1,3,#,5,4}

说明

    1
     \
      3
     / \
    4   5




变为





    1
     \
      3
     / \
    5   4




变为





        1
       /
      3
     / \
    5   4

备注:
树的节点个数在之间，且保证该树上每个节点的编号不同，节点编号并非按顺序排列，。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
好难取个名字头像 好难取个名字 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    class Node{
        int parentIndex;
        int currentIndex;
        int flag;//0:左孩子 1：右孩子
        TreeNode currentNode;
        public Node(int parentIndex, int currentIndex, int flag, TreeNode currentNode){
            this.parentIndex = parentIndex;
            this.currentIndex = currentIndex;
            this.flag = flag;
            this.currentNode = currentNode;
        }
    }
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        // write code here
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0,0,root));
        int parentNum = 1,nextNum = 0;
        ArrayList<Node> temp_list = new ArrayList<>();
        while(queue.size() != 0){
            Node node = queue.poll();
            temp_list.add(node);
            --parentNum;
            if(node.currentNode.left != null){
                queue.offer(new Node(node.currentIndex,nextNum++,0,node.currentNode.left));
            }
            if(node.currentNode.right != null){
                queue.offer(new Node(node.currentIndex,nextNum++,1,node.currentNode.right));
            }
            if(parentNum == 0){
                parentNum = nextNum;
                nextNum = 0;
                list.add(temp_list);
                temp_list = new ArrayList<>();
            }
        }
        int deep = list.size() - 1;
        for(int i = deep; i >= 1; --i){
            ArrayList<Node> parent_list = list.get(i-1);
            int parent_level_sum = parent_list.size();
            for(Node node : parent_list){
                node.currentNode.left = null;
                node.currentNode.right = null;
            }
            int move = k % (2*parent_level_sum);
            temp_list = list.get(i);
            for(Node node : temp_list){
                int target_parent_location = node.flag == 0? 
                    (node.parentIndex+move/2)%parent_level_sum : (node.parentIndex+(move+1)/2)%parent_level_sum;
                int target_child_flag = node.flag == 0? move % 2 : (move + 1) % 2;
                Node parentNode = parent_list.get(target_parent_location);
                if(target_child_flag == 0) parentNode.currentNode.left = node.currentNode;
                else parentNode.currentNode.right = node.currentNode;
            }
        }
        
        return root;
    }
}

发表于 2022-08-05 12:25:59 回复(0)
tach1koma头像 tach1koma 
class Solution {
private:
    void rightShiftLayer(vector<TreeNode *> &layer, int k) {
        int n = layer.size();
        k %= n;
        reverse(layer.begin(), layer.end());
        reverse(layer.begin(), layer.begin() + k);
        reverse(layer.begin() + k, layer.end());
    }
public:
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        if (!root)
            return root;
        stack<vector<TreeNode *>> allLayers;
        vector<TreeNode *> prevLayer, currLayer;
        prevLayer.push_back(root);
        while (!prevLayer.empty()) {
            for (TreeNode *node : prevLayer) {
                if (node) {
                    currLayer.push_back(node->left);
                    currLayer.push_back(node->right);
                }
            }
            allLayers.push(prevLayer);
            prevLayer = currLayer;
            currLayer.clear();
        }
        allLayers.pop();
        currLayer = allLayers.top();
        allLayers.pop();
        while (!allLayers.empty()) {
            prevLayer = allLayers.top();
            allLayers.pop();
            rightShiftLayer(currLayer, k);
            int idx = 0;
            for (TreeNode *node : prevLayer) {
                if (node) {
                    node->left = currLayer[idx++];
                    node->right = currLayer[idx++];
                }
            }
            currLayer = prevLayer;
        }
        return root;
    }
};
发表于 2022-01-15 10:58:46 回复(0)
牛客565952260号头像 牛客565952260号
全部ac。 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        // write code here
        if (root == nullptr)
        {
            return root;
        }
        vector<deque<pair<TreeNode*, int>>> layers;
        deque<pair<TreeNode*, int>> layer;
        layer.emplace_back(root, 1);
        while (!layer.empty())
        {
            layers.push_back(layer);
            int size = layer.size(), pos = 0;
            while (pos < size)
            {
                TreeNode* node = layer.front().first;
                layer.pop_front();
                if (node->left != nullptr)
                {
                    layer.emplace_back(node->left, pos * 2);
                }
                if (node->right != nullptr)
                {
                    layer.emplace_back(node->right, pos * 2 + 1);
                }
                node->left = nullptr;
                node->right = nullptr;
                ++pos;
            }
        }
        while (layers.size() > 1)
        {
            deque<pair<TreeNode*, int>> down = layers.back();
            layers.pop_back();
            deque<pair<TreeNode*, int>>& up = layers.back();
            int width = up.size() * 2;
            while (!down.empty())
            {
                int old_pos = down.front().second;
                TreeNode* node = down.front().first;
                down.pop_front();
                int tmp = old_pos + k;
                int new_pos = (tmp % width) / 2;
                
                if ((tmp & 1) == 0)
                {
                    up[new_pos].first->left = node;
                }
                else
                {
                    up[new_pos].first->right = node;
                }
            }
            
        }
        return root;
        
        
    }
};

编辑于 2022-03-08 14:59:44 回复(2)
zzzin头像 zzzin 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        // write code here
        if(root==null){return root;}
        List<List<TreeNode>> cengxu = new ArrayList();
        Queue<TreeNode> bfs = new LinkedList();
        bfs.add(root);
        List<TreeNode> diyiceng = new ArrayList();
        diyiceng.add(root);
        cengxu.add(diyiceng);
        while(!bfs.isEmpty()){
            int n=bfs.size();
            List<TreeNode> tmp = new ArrayList();
            for(int i=0;i<n;i++){
                TreeNode t=bfs.poll();
                tmp.add(t.left);
                tmp.add(t.right);
                if(t.left!=null){bfs.add(t.left);}
                if(t.right!=null){bfs.add(t.right);}
            }
            cengxu.add(tmp);
        }
        int n=cengxu.size();
        for(int i=n-3;i>=0;i--){
            List<TreeNode> thisfloor=cengxu.get(i);
            List<TreeNode> nextfloor=cengxu.get(i+1);
            int thissize=thisfloor.size();
            int nextsize=nextfloor.size();
            int kk=k%nextsize;
            for(int j=0;j<thissize;j++){
                if(thisfloor.get(j)==null){continue;}
                int x1=(2*j+nextsize-kk)%nextsize;
                int x2=(2*j+nextsize-kk+1)%nextsize;
                thisfloor.get(j).left=nextfloor.get(x1);
                thisfloor.get(j).right=nextfloor.get(x2);
            }
        }
        return root;
    }
}
上面的代码只通过了4/19；我不是连续做的，做一个休息一会，这题看着麻烦就是最后一个写的，没时间改了
发表于 2021-10-24 21:16:43 回复(0)
Java
杨提督的红茶头像 杨提督的红茶 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        // 存储第一层节点
        Queue<TreeNode> queue1 = new LinkedList<>();
        // 存储第一层节点的子节点
        Queue<TreeNode> queue2 = new LinkedList<>();
    
        queue1.offer(root);
        addNode(queue2, root);

        while (!queue1.isEmpty()) {
            int size = queue1.size();

            moveK(queue1, k);
            moveK(queue2, k);

            while (size > 0) {
                changeNode(queue1, queue2);
                size--;
            }
        }
        return root;
    }

    public static void changeNode(Queue<TreeNode> queue1, Queue<TreeNode> queue2) {
        // 取出根节点 tmp
        TreeNode tmp = queue1.poll();

        // 为根节点添加子节点，当子节点val为0时，子节点为空
        TreeNode childLeft = queue2.poll();
        if (childLeft.val == 0) {
            tmp.left = null;
        }else {
            queue1.offer(childLeft);
            tmp.left = childLeft;
            addNode(queue2, childLeft);
        }

        TreeNode childRight = queue2.poll();
        if (childRight.val == 0) {
            tmp.right = null;
        }else {
            queue1.offer(childRight);
            tmp.right = childRight;
            addNode(queue2, childRight);
        }
}

    // 右移 k 位
    public static void moveK(Queue<TreeNode> queue, int k) {
        while (k > 0) {
            queue.offer(queue.poll());
            k--;
        }
    }

    // 添加节点
    public static void addNode(Queue<TreeNode> queue, TreeNode root) {
        if (root.val == 0) {
            return;
        }
        //  为了使得叶子节点，在右移的过程中获得子节点，将null转换为 val=0 的子节点，之后再识别出来，转化为null
        if (root.left != null) {
            queue.offer(root.left);
        }else {
            queue.offer(new TreeNode(0));
        }

        if (root.right != null) {
            queue.offer(root.right);
        }else {
            queue.offer(new TreeNode(0));
        }
  
    }

}

发表于 2023-02-18 13:19:47 回复(0)
2U==头像 2U==
python简单代码 
class Solution:
    def cyclicShiftTree(self,root:TreeNode,k:int):
        q=[[root]]
        cur=[root]
        while cur:
            tmp=[]
            for node in cur:
                if node is None:continue
                tmp.append(node.left)
                tmp.append(node.right)
            q.append(tmp)
            cur=tmp
        lv=len(q)
        for i in range(lv-2,-1,-1):
            #i,i+1
            m=len(q[i+1])
            tmp=[None]*m
            for j in range(m):
                new_j=(j+k)%m
                tmp[new_j]=q[i+1][j]
            idx=0
            for node in q[i]:
                if node is None:continue
                node.left=tmp[idx]
                node.right=tmp[idx+1]
                idx+=2
        return q[0][0]


发表于 2022-10-19 21:46:17 回复(0)
牛客979566589号头像 牛客979566589号

极简递归思路

    定义一片二叉森林是一个有序二叉树序列。去除森林所有根节点后，全体子树构成的森林被称为子树森林。显然二叉森林的子树森林也是二叉森林。    
    将输入的树看作一片只有一棵二叉树的森林，问题转化为对二叉森林的每层节点进行循环右移，其思路如下：
  1. 循环右移子树森林每层的所有节点，形成新的子树森林
  2. 根结点与新子树森林组合，形成新的二叉森林
  3. 对二叉森林中的每颗树进行循环右移（等价于对根节点进行循环右移）
    python代码如下：
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param k int整型 
# @return TreeNode类
#
class Solution:
    def cyclicShiftTree(self , root , k ):
        forest = [root]                         # 将输入的二叉树表示为森林
        return Solution.cycShiftForest(forest,k)[0]                    # 输出处理好的二叉森林，依然只有一棵树
    
    @staticmethod
    def cycShiftForest(forest:list,k:int)->list:    # 将森林的每层节点循环右移k位
        if len(forest)>0: 
           # 收集所有子树，构成子树森林
            subforest=[]
            for tree in forest:
                if tree is not None:
                    subforest.append(tree.left)
                    subforest.append(tree.right)
            
            subforest = Solution.cycShiftForest(subforest,k) # 循环右移子树森林的每层结点
            
            index = 0                                        # 根节点与子树森林重新拼接成新的森林
            for root in forest:
                if root is not None:
                    root.left = subforest[index]
                    root.right = subforest[index+1]
                    index += 2
            forest = Solution.cycMove(forest,k)               # 再对新森林的每颗树进行循环右移
        return forest
    
    # cycMove将list内元素循环右移offset个单位
    @staticmethod
    def cycMove(L:list,offset:int)->list:
        offset = offset % len(L)
        if offset > 0 :
            _L = L[-offset-1::-1]
            _L += L[-1:-offset-1:-1]
            _L = _L[::-1]
        else:
            _L = L
        return _L


发表于 2022-08-17 10:30:19 回复(0)
C++
牛客591847084号头像 牛客591847084号
求大神指导为啥下方的代码只能运行通过50%的案例。 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    

    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        // write code here
        deque<TreeNode*> q;
        deque<int> level_q, level_index_q;
        vector<vector<TreeNode*>> level_map;
        int level = 0;
        int level_index = 0;
        while (root != nullptr) {
            // visit root;
            // cout << root->val << " ";
            int level_max = pow(2, level);
            if (level == level_map.size()) {
                level_map.push_back(vector<TreeNode*>(level_max, nullptr));
            }
            level_map[level][level_index] = root;
            // 
            if (root->left != nullptr) {
                q.push_back(root->left);
                level_q.push_back(level+1);
                level_index_q.push_back(level_index * 2);
            }
            if (root->right != nullptr) {
                q.push_back(root->right);
                level_q.push_back(level+1);
                level_index_q.push_back(level_index * 2 + 1);
            }
            if (q.empty()) {
                break;
            }
            root = q.front();
            level = level_q.front();
            level_index = level_index_q.front();
            q.pop_front();
            level_q.pop_front();
            level_index_q.pop_front();
        }
        
        
        for (auto& item : level_map) {
            for (auto& node : item) {
                if (node == nullptr) {
                    cout << "# ";
                }
                else {
                    cout << node->val << " ";
                    node->left = nullptr;
                    node->right = nullptr;
                }
            }
            cout << endl;
        }
        cout << endl;
        
        for(int child_level = level_map.size() - 1; child_level > 0; --child_level){
            auto parent_level = child_level - 1;
            int k_shift = k;
            for (int child_index = 0; child_index < level_map[child_level].size(); ++child_index){
                auto& child_node = level_map[child_level][child_index];
                if (child_node ==nullptr) continue;
                int new_child_index = (child_index + k_shift) % level_map[child_level].size();
                int parent_index = new_child_index / 2;
                if (new_child_index % 2 == 0) {
                    while (level_map[parent_level][parent_index] == nullptr 
                           || level_map[parent_level][parent_index]->left != nullptr)
                        parent_index = (parent_index + 1) % level_map[parent_level].size();
                    level_map[parent_level][parent_index]->left = child_node;
                }
                else {
                    while (level_map[parent_level][parent_index] == nullptr 
                           || level_map[parent_level][parent_index]->right != nullptr)
                        parent_index = (parent_index + 1) % level_map[parent_level].size();
                    level_map[parent_level][parent_index]->right = child_node;
                }
            }
        }
        root = level_map[0][0];
        return root;
    }
};


发表于 2022-02-14 12:51:44 回复(0)
不敢填，怕换不掉头像 不敢填，怕换不掉 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param k int整型
     * @return TreeNode类
     */
             
    void getChild(const vector<TreeNode *>& parentVector, int k ){
 
        vector<TreeNode *> child;

        if (parentVector.empty() ){ 

            return;
        }
         
        for (unsigned int i = 0; i < parentVector.size(); i++ ) {
             
            TreeNode* node = parentVector.at(i);
             
            if (node != nullptr) {
 
                child.push_back( node -> left );
                child.push_back( node -> right );   
            }
 
        }
         
         
        getChild(child, k);       ////////////     recursion
 
        int indexShift = k;  
        if ( indexShift >= child.size() && child.size() != 0) {
                indexShift %= child.size() ;               
        }
         
        if (indexShift >= 1){         ///////    if  shift == child.size(), NO  shifting
                indexShift = child.size() - indexShift;
        }
         
        for (unsigned int i = 0; i < parentVector.size(); i++ ) {
             
            if ( parentVector.at(i) != nullptr ) {
                 
                parentVector.at(i) -> left = child.at(indexShift);
                indexShift++;
 
                if (indexShift >= child.size() ) {  //    reset  indexShift  if  over child.size()
                    indexShift = 0;
 
                }
 
                parentVector.at(i) -> right = child.at(indexShift);
                indexShift++;
 
                if (indexShift >= child.size() ) {
                    indexShift = 0;
                }
            }
        }
    }
     
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        // write code here
        vector<TreeNode *> parent = {}; //{root};    /////   EMPTY  Vector
        parent.push_back(root);
         
        getChild(parent, k);

        return root;
    }
};

发表于 2022-01-18 15:16:07 回复(0)
pein531头像 pein531
这个题……难就算了，还卡常数时间，同样的逻辑非得C++来一遍才能AC
发表于 2022-01-05 16:06:05 回复(1)
Java
别卷了会猝死的头像 别卷了会猝死的
同样的逻辑 java超时  c++A了😥
发表于 2021-12-24 21:02:22 回复(0)
超级大米头像 超级大米
这题题目也没说
万一k=1 而且是这样的结构 
      1
       \
        3
       / \
      4   5
怎么办
5移动之后不就傻了吗
发表于 2021-12-07 20:25:36 回复(1)
提交观点

问题信息

树
上传者：小小
难度：
12条回答 3134浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号