如何从四叉树深度优先遍历结果重建结构并计算x、y偏移量

不需要在编码阶段额外存储x、y偏移量，利用四叉树递归分块的特性，直接在遍历过程中就能算出每个叶子节点对应的坐标，核心逻辑基于四叉树的层级分块规则：

首先统一遍历顺序约定（和绝大多数图像类四叉树编码的DFS顺序一致），每一层的四个子节点按固定顺序对应四个等大的子象限，每个子块边长是当前层块边长的1/2：

• 第一个遍历的子节点：左上象限，相对父块的x偏移为0，y偏移为0
• 第二个遍历的子节点：右上象限，相对父块的x偏移为当前层子块边长，y偏移为0
• 第三个遍历的子节点：左下象限，相对父块的x偏移为0，y偏移为当前层子块边长
• 第四个遍历的子节点：右下象限，相对父块的x偏移为当前层子块边长，y偏移为当前层子块边长

具体实现步骤：

1. 初始化阶段确定矩阵总边长（比如示例中的256），根节点对应覆盖整个矩阵，初始偏移x=0、y=0，块边长等于总边长。
2. 按深度优先顺序逐节点访问：
   • 如果当前节点是叶子节点（块边长为1），当前维护的x、y值就是该节点值对应的写入坐标，直接填入矩阵即可
   • 如果当前节点是内部节点，将块边长折半，按约定的四个象限顺序，依次给每个子节点计算对应的起始偏移，递归/迭代访问子节点即可
3. 迭代实现时只需要用栈存储每个待访问节点的起始x偏移、起始y偏移、对应块边长三个参数，不需要额外的存储开销；递归实现直接传参即可，回溯时不需要额外处理偏移回退，因为参数是按调用栈隔离的。

参考实现代码如下：

import numpy as np

def rebuild_quadtree_matrix(dfs_sequence, total_size=256, dtype=np.int32):
    """
    从四叉树深度优先遍历序列重建2D矩阵
    dfs_sequence: 按DFS顺序排列的节点序列，叶子节点存储实际像素值，非叶子节点可标记为None
    total_size: 输出矩阵的边长，需为2的整数次幂
    """
    matrix = np.empty((total_size, total_size), dtype=dtype)
    seq_ptr = 0  # 遍历序列的移动指针

    def dfs(node_x_off, node_y_off, cur_block_size):
        nonlocal seq_ptr
        current_node = dfs_sequence[seq_ptr]
        seq_ptr += 1
        # 叶子节点：块大小为1，直接写入对应坐标
        if cur_block_size == 1:
            matrix[node_y_off, node_x_off] = current_node
            return
        # 非叶子节点：折半拆分块，按象限顺序遍历子节点
        half_size = cur_block_size // 2
        dfs(node_x_off, node_y_off, half_size)  # 左上
        dfs(node_x_off + half_size, node_y_off, half_size)  # 右上
        dfs(node_x_off, node_y_off + half_size, half_size)  # 左下
        dfs(node_x_off + half_size, node_y_off + half_size, half_size)  # 右下

    dfs(0, 0, total_size)
    return matrix

如果编码阶段采用的象限遍历顺序和上述约定不同，只需要调整四个子节点的偏移计算顺序即可，核心推导逻辑不需要改动。该方法的时间复杂度和提前存储偏移量的实现完全一致，都是O(n²)，没有额外性能损耗。

内容的提问来源于stack exchange，提问作者Jackie Carson