51. 平移二叉树

// 思路如下：
// 先澄清一个误区
// 题目中说要从下往上平移
// 但实际上从上往下平移结果也是一样的
// 因为无论是从上往下还是从下往上,每一层节点被平移的次数是固定的
// 我们先读入数据并且根据数据构造二叉树
// 然后从二叉树的顶层从上往下读取每一层的数据
// 接下来将该层数据存入一个数组并将该数组中的元素向右平移k位
// 打印平移后的数据并将下一层的数据存入队列中

#include <bits/stdc++.h>
using namespace std;

int k, n;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val = 0) : val(val), left(nullptr), right(nullptr) {}
};
// 将数组中的元素向右平移k位
// 下方代码若不懂可自行模拟一下
// reverse(right.begin(), right.end())的意思是翻转字符串开头到结尾的字符,依此类推
void go_right(vector<TreeNode*>& right, int k) {
    k = k  % right.size();
    reverse(right.begin(), right.end());
    reverse(right.begin(), right.begin() + k);
    reverse(right.begin() + k, right.end());
}

void solve() {
    int size = 1; // 用来表示当前层的节点数
    TreeNode* head;
    queue<TreeNode*> que;
    // 读入数据并构造二叉树
    while(n) {
        vector<TreeNode*> s(size); // 用来储存当前层的所有节点
        int nsize = 0; // 下一层节点的个数
        int cnt = 0; // 当前已读入节点的个数
        int tmp; // 用来临时存放数据
        while(cin >> tmp) {
            // 初始化一个新节点并加入当前层中
            s[cnt] = new TreeNode(tmp);
            // 如果该节点值不是-1,则说明将会有2个孩子
            if(tmp != -1) nsize += 2;
            cnt++;
            // 若cnt == size, 则本层所有节点均已读入完毕
            if(cnt == size) break;
        }
        int qsize = que.size();
        int cur = 0;
        // que中存储的是上一层节点的数据
        // 我们需要将上一层节点与本层节点建立连接
        while(qsize--) {
            TreeNode* t = que.front();
            que.pop();
            // 跳过节点值为-1的节点,因为它没有左右节点
            if(t->val == -1) continue;
            t->left = s[cur];
            t->right = s[cur + 1];    
            que.push(s[cur]);
            que.push(s[cur + 1]);
            cur += 2;
        }
        // 若size == 1则说明现在读入的数据是第一个节点
        // 执行初始化操作
        if(size == 1) {
            head = new TreeNode(s[0]->val);
            que.push(head);
        }
        // 减去已经读入的节点数,当n = 0时结束循环
        n -= size;
        // 将下一层的节点值赋给size
        size = nsize;
    }
    que = queue<TreeNode*>();
    que.push(head);
    // 平移并输出答案
    // 思路如下：
    // 从上往下读取每一层的节点并暂存在数组中
    // 将数组中的元素向右平移k位
    // 输出平移后的结果并将其左右节点存入que中
    while(!que.empty()) {
        int qsize = que.size();
        vector<TreeNode*> s(qsize);
        for(int i = 0; i < qsize; ++i) {
            s[i] = que.front();
            que.pop();
        }
        go_right(s, k);
        for(int i = 0; i < s.size(); ++i) {
            cout << s[i]->val << " ";
            if(s[i]->left) {
                que.push(s[i]->left);
            }
            if(s[i]->right) {
                que.push(s[i]->right);
            }
        }
    }
    cout << endl;
}

int main() {
    while(cin >> k >> n) {
        solve();    
    }
    return 0;
}

/**
 * 总体上的思路：
 * 首先，将二叉树的节点按照层级关系放置到二维数组中（简化问题），
 * 每一层的节点都放在数组的一个一维数组中，同时保持树的左右关系。
 * 
 * 然后，从后向前遍历二维数组。
 * 从最底层的一维数组开始，对每个一维数组中的元素进行平移操作，可以通过取模实现循环平移的功能。
 * 
 * 最后，完成本层一维数组的平移之后，上升到上一层级的一维数组，重复执行平移操作，以此类推。
*/
import java.util.*;

public class Main {
    // 静态内部类
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode () {}
        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        // 输入数据
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int N = scanner.nextInt();
        for (int i = 0; i < N; i++) {
            list.add(scanner.nextInt());
        }
        // 记录节点所在层级
        Map<TreeNode, Integer> map = new HashMap<>();
        // 根据规定的顺序创建二叉树
        TreeNode root = generateBinaryTree(list);
        // 移动二叉树
        cyclicShiftTree(root, k, map);
        // 打印循环移动后的二叉树
        leverOrderTraversal(root);
    }

    // 创建二叉树
    public static TreeNode generateBinaryTree(List<Integer> list) {
        if (list.isEmpty()) return null;  // 如果列表为空，则返回空节点
        // 创建根节点
        TreeNode root = new TreeNode(list.get(0));
        // 从第二个节点开始构建二叉树
        int index = 1;
        // 创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty() && index < list.size()) {
            // 拿出队列首部的节点
            TreeNode currentNode = queue.poll();
            // 构建左子树
            if (index < list.size()) {
                if (list.get(index) != -1) {  // 如果不是空节点
                    currentNode.left = new TreeNode(list.get(index));
                    queue.offer(currentNode.left);
                }
                index++;  // index 不可放入判断条件内...
            }
            // 构建右子树
            if (index < list.size()) {
                if (list.get(index) != -1) {  // 如果不是空节点
                    currentNode.right = new TreeNode(list.get(index));
                    queue.offer(currentNode.right);
                }
                index++;
            }
        }
        return root;
    }

    /**
     * 功能：将二叉树放置到二维数组上，并将每个节点在它自己层级的那个一维数组的中的位置保存到 map 中。
    */
    public static List<List<TreeNode>> treeStructureTo2DArray(TreeNode root, Map<TreeNode, Integer> map) {
        List<List<TreeNode>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<TreeNode> row = new ArrayList<>();
            int index = 0;
            // 逐层遍历，不要一次遍历完
            for (int i = queue.size(); i > 0; i--) {
                TreeNode currentNode = queue.poll();
                index++;
                // 如果当前节点是空节点，那么它就没有左右孩子需要处理
                if (currentNode.val == -1) {
                    continue;
                }
                // 将当前节点加入到这一层的一维数组中
                row.add(currentNode);
                // 记录当前节点在这一层中的位置
                map.put(currentNode, index - 1);
                
                // 以下九行代码的意图是维持二叉树的结构
                // 和输入数据使用 -1 代表空节点的意图一致
                if (currentNode.left == null) {
                    queue.offer(new TreeNode(-1));
                } else {
                    queue.offer(currentNode.left);
                }

                if (currentNode.right == null) {
                    queue.offer(new TreeNode(-1));
                } else {
                    queue.offer(currentNode.right);
                }
                // 将父节点与子节点之间的链接断开
                // 因为逐层平移以后也会断开
                currentNode.left = null;
                currentNode.right = null;
            }
            // 本层处理完毕
            result.add(row);
        }
        return result;
    }

    // 移动二叉树
    public static TreeNode cyclicShiftTree(TreeNode root, int k, Map<TreeNode, Integer> map) {
        List<List<TreeNode>> twoDArray = treeStructureTo2DArray(root, map);
        for (int i = twoDArray.size() - 1; i > 0; i--) {  // 自底向上，依次移动
            List<TreeNode> child = twoDArray.get(i);
            List<TreeNode> parent = twoDArray.get(i - 1);
            for (int j = 0; j < child.size(); j++) {
                TreeNode chi = child.get(j);
                // 计算父节点
                // 先看 parent.size() * 2
                // 上一层级的每个节点都能给当前层级的所有节点提供两格平移的空间（左孩子和右孩子）
                // map.get(chi) + k 为向右平移 k 个位置
                // 最后需要 / 2，思考一下完全二叉树是如何查找父节点的
                TreeNode par = parent.get((map.get(chi) + k) % (parent.size() * 2) / 2);
                // 判断奇偶性，确定左右节点，然后将当前节点连上平移后的父节点
                if ((map.get(chi) + k) % (parent.size() * 2) % 2 == 0) {
                    par.left = chi;
                } else {
                    par.right = chi;
                }
            }
        }
        return root;
    }

    // 以层序遍历的方式打印二叉树
    public static void leverOrderTraversal(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queue1 = new LinkedList<>();
        queue.offer(root);
        queue1.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current.left != null) {
                queue.offer(current.left);
                queue1.offer(current.left.val);
            } else {
                queue1.offer(-1);
            }
            if (current.right != null) {
                queue.offer(current.right);
                queue1.offer(current.right.val);
            } else {
                queue1.offer(-1);
            }
        }
        for (int i = queue1.size(); i > 0; i--) {
            System.out.printf("%d%c", queue1.poll(), i == 1 ? '\n' : ' ');
        }
    }
}

k, n = map(int, input().split())
arr = list(map(int, input().split()))


def reverse(i, j):
    j -= 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1


def shift(i, j, k):
    l = j - i
    k %= l
    reverse(i, j-k)
    reverse(j-k, j)
    reverse(i, j)


cnt = 0  # 统计该层非空节点个数
start = 0  # 该层第一个节点索引
next_ = 0  # 该层最后一个节点索引
kk = 0  # 该层右移次数，根节点这一层只有一个，不需要平移
for i, num in enumerate(arr):
    # 统计当前层有多少非空节点
    if num != -1:
        cnt += 1
    # 到了当前层的末尾
    if i == next_:
        kk %= next_ + 1 - start
        # 统计当前层有多少非空节点从右侧移出到左侧
        shift_node_cnt = len(
            [j for j in range(next_ + 1 - kk, next_+1) if arr[j] != -1])
        # 右移当前层
        shift(start, next_ + 1, kk)
        # 当前层每多一个非空节点右移出到左侧，则下一层应多右移2次
        # 更新下一层右移次数
        kk = k + shift_node_cnt * 2
        # 更新下一层节点的索引并清空统计值
        start = i + 1
        next_ += cnt << 1
        cnt = 0
print(' '.join(map(str, arr)))