描述

题目描述

首先是给了我们一颗二叉树，然后给了我们一个$kk$的值，然后让我们去把整棵树的每一层都向右移动$kk$个

如果大家对二叉树不理解，可以先看一下牛客的这一道题目和这道题目我的题解

修建叶子-(传送门)

样例解释

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

这里我们拿好看的图解来解释一下这个问题

然后我们第一步是移动最底下的一层的节点，那么我们$4,54,\; 5$向右移动一位，我们可以发现他们俩其实就是交换了一个位置，那么我们画出来这个图

我们可以得到这么一个树

然后我们移动第二层，就是我们的把空节点和$33$号节点移动一下，我们可以得到下面的这个树

所以我们最后的结果就是

{1,3,#,5,4}

题解

这里会给出三种语言的题解，分别是C++, Java，Python

解法一：Python

解题思路：

这里我拿我的这个Python的代码来讲思路，首先我们还是拿我在前面讲的样例来说明，第一个我们先把根节点放到一个'数组'我们称之为临时节点数组

这里我们不考虑八股文，我们统一称之为数组

然后我们把父亲节点数组颠倒，我们使用数组的裁剪就可以了，然后我们把临时节点的子节点全部放入一个名字位儿子节点数组中，然后我们把我们临时数组里面的元素赋值给我们父亲数组的左右节点，然后我们把临时数组赋值给我们的父亲数组，然后儿子数组赋值给了我们的临时数组，这样我们可以实现这么一个操作，就是我们每次从上往下交换，然后我们再把底下的元素归位即可

这里强烈推荐大家拿纸按照我的代码，拿我解释的样例多多模拟几遍，真的会豁然开朗

代码实现：

class Solution:
    def cyclicShiftTree(self, root, k):
        deque = [root]
        # 放入我们的根节点
        fatherRoot = []
        while deque:
            n = k % len(deque)
            deque = deque[len(deque) - n:] + deque[:len(deque) - n]
            # 这里我们直接把上一层颠倒
            sonRoot = []
            for i in deque:
                if i:
                    sonRoot.append(i.left)
                    sonRoot.append(i.right)
            # 把我们的节点连接的产生的节点放在一起
            idx = 0
            for i in fatherRoot:
                if i:
                    i.left = deque[idx]
                    idx = idx + 1
                    i.right = deque[idx]
                    idx = idx + 1
            # 这里把我们的子节点重新归位
            fatherRoot = deque
            deque = sonRoot
        return root

时空复杂度：

时间复杂度： $O(n)O(n)$

理由如下：我们可以发现，我们每一个节点是平均会使用两次，所以我们的时间复杂度跟我们的节点数量有关，常数忽略，所以我们最后的时间复杂度是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：我们发现我们其实开辟的数组把我们所有的节点都存储过了，所以我们最后所需要的空间也是和我们的节点数有关系，所以最后我们的空间复杂度就是$O(n)O(n)$

解法二：Java（超时）

Java这个可能写这个题目的同学都会超时在第九个测试点，这个没有办法，我尝试用数组手写双端队列，但是还是在第九个点超时了，这个可能是跟Java的语言特性有关系，但是不代表我们没法子学到东西

解题思路：

这里我们跟Python其实是有一定区别的，我们Python是从头开始到底下，我们的这个思路有点相反，我们先向下遍历，确定树的深度，然后我们从最后的一层开始进行一个交换

这里主要讲的就是我们交换的思路：如何交换

举个栗子：

1 2 3 4 5
1

我们把上面的这个序列我们循环向右移动一位，我们如何做呢？

第一种思路： （当前位置 + 移动距离） % 总体长度

第二种思路： 先找到终端点，然后我们把中断点的左边旋转，右边旋转，最后整体旋转即可

代码实现：

import java.util.*;
public class Solution {
    public static TreeNode[] deque = new TreeNode[1000010];
//     因为Java的速度真的慢，这里我们手写双端队列
    public static int[] ends = new int[110];
    
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        int l = 0, r = 0;
//         双端队列的头和尾，这里手动模拟了
        deque[r++] = root;
//         头节点入队
        int h = 0;
//         这个可以理解是这颗树的深度
        while(l != r) {
            ends[h] = r;
            while(l < ends[h]) {
                TreeNode tmp = deque[l++];
                if (tmp != null) {
                    deque[r++] = tmp.left;
                    deque[r++] = tmp.right;
                }
            }
            h++;
        }
//         我们这段可以理解是把每一层的给他存储来，方便我们日后使用
        for (int i = h - 1; i > 0; i--) {
//             从我们这颗树的底下开始遍历
            int sonLeft = ends[i - 1], sonRight = ends[i] - 1;
            int sonLength = k % (sonRight - sonLeft + 1);
            int idx = sonLength == 0 ? sonLeft : (sonRight - sonLength + 1);
//             这里我们确定我们的左边界，有边界，和我们中间开始断掉的点
            int fLeft = i - 2 >= 0 ? ends[i - 2] : 0, fRight = ends[i - 1] - 1;
            for (int j = fLeft; j <= fRight; j++) {
                if (deque[j] != null) {
                    deque[j].left = deque[idx];
                    idx = idx == sonRight ? sonLeft : idx + 1;
                    deque[j].right = deque[idx];
                    idx = idx == sonRight ? sonLeft : idx + 1;
                }
            }
//             交换的操作
        }
        return root;
    }
}

时空复杂度：

时间复杂度： $O(n)O(n)$

理由如下：我们可以发现，我们每一个节点是平均会使用常数次，所以我们的时间复杂度跟我们的节点数量有关，常数忽略，所以我们最后的时间复杂度是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：我们发现我们其实开辟的数组把我们所有的节点都存储过了，所以我们最后所需要的空间也是和我们的节点数有关系，所以最后我们的空间复杂度就是$O(n)O(n)$

解法三：C++ (yyds) 速度嘎嘎滴

解题思路：

这里没什么多说的了，思路就是和Java是一致的了

代码实现：

class Solution {
public:
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        deque<TreeNode*> dq;
        vector<int> ends(110);
        int l = 0, h = 0;
        dq.push_back(root);
        while(l != dq.size()) {
            ends[h] = dq.size();
            while(l < ends[h]) {
                TreeNode* tmp = dq[l++];
                if (tmp != nullptr) {
                    dq.push_back(tmp->left);
                    dq.push_back(tmp->right);
                }
            }
            h++;
        }
        for (int i = h - 1; i > 0; i--) {
//             从树下开始遍历
            int sonLeft = ends[i - 1], sonRight = ends[i] - 1;
            int sonLength = k % (sonRight - sonLeft + 1);
            int idx = sonLength == 0 ? sonLeft : (sonRight - sonLength + 1);
//             这里我们确定我们的左边界，有边界，和我们中间开始断掉的点
            int fLeft = i - 2 >= 0 ? ends[i - 2] : 0, fRight = ends[i - 1] - 1;
            for (int j = fLeft; j <= fRight; j++) {
                if (dq[j] != nullptr) {
                    dq[j]->left = dq[idx];
                    idx = idx == sonRight ? sonLeft : idx + 1;
                    dq[j]->right = dq[idx];
                    idx = idx == sonRight ? sonLeft : idx + 1;
                }
            }
        }
        return root;
    }
};

时空复杂度：

时间复杂度： $O(n)O(n)$

理由如下：我们可以发现，我们每一个节点是平均会使用常数次，所以我们的时间复杂度跟我们的节点数量有关，常数忽略，所以我们最后的时间复杂度是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：我们发现我们其实开辟的数组把我们所有的节点都存储过了，所以我们最后所需要的空间也是和我们的节点数有关系，所以最后我们的空间复杂度就是$O(n)O(n)$