求基于任意层序遍历数组重建二叉树的通用解决方案

问题背景 #

给定一个表示二叉树（非二叉搜索树）层序遍历的数组，其中x代表空节点，需要重建对应的二叉树。例如输入[6,x,8,4,x]，重建后树的结构为：根节点6的右子节点是8，8的左子节点是4。

传统方案中用2i+1和2i+2访问下标i节点的左右子节点，这种方式仅适用于完全二叉树，比如上述示例要改成[6,x,8,x,x,4,x]才能适配。我们需要一种能处理任意输入的通用解法。

已知TreeNode类结构如下：

class TreeNode{
  String value;
  TreeNode left;
  TreeNode right;
}

最终返回重建后树的根节点即可。

通用解决方案：基于队列的层序构建法 #

核心思路是用队列跟踪所有需要分配子节点的非空节点，按层序遍历的顺序依次为每个节点分配左右子节点，完全适配非完全二叉树的场景。

步骤说明

1. 若输入数组为空，直接返回null。
2. 创建根节点（数组第一个元素），并将其加入队列。
3. 用一个指针index从数组的第二个元素（下标1）开始遍历。
4. 循环处理队列中的节点：
   • 取出队首节点作为当前待处理节点。
   • 处理左子节点：如果index未超出数组长度，且当前元素不是x，则创建左子节点并挂载到当前节点，同时将该左子节点加入队列；无论是否创建，index都后移一位。
   • 处理右子节点：如果index未超出数组长度，且当前元素不是x，则创建右子节点并挂载到当前节点，同时将该右子节点加入队列；无论是否创建，index都后移一位。
5. 当队列空或index遍历完数组时，结束循环，返回根节点。

代码实现（Java）

import java.util.LinkedList;
import java.util.Queue;

public class TreeBuilder {
    public TreeNode buildTree(String[] levelOrder) {
        if (levelOrder == null || levelOrder.length == 0) {
            return null;
        }

        // 创建根节点并加入队列
        TreeNode root = new TreeNode(levelOrder[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int index = 1;
        while (!queue.isEmpty() && index < levelOrder.length) {
            TreeNode current = queue.poll();

            // 处理左子节点
            if (!"x".equals(levelOrder[index])) {
                TreeNode leftNode = new TreeNode(levelOrder[index]);
                current.left = leftNode;
                queue.add(leftNode);
            }
            index++;

            // 处理右子节点，需先判断index是否越界
            if (index < levelOrder.length && !"x".equals(levelOrder[index])) {
                TreeNode rightNode = new TreeNode(levelOrder[index]);
                current.right = rightNode;
                queue.add(rightNode);
            }
            index++;
        }

        return root;
    }
}

方案解释

• 队列的作用是维护当前层中所有非空节点，确保我们按层序的顺序为每个节点分配子节点，不会跳过或错误关联。
• 空节点（x）不会被加入队列，避免了为不存在的节点分配子节点的情况，完美适配非完全二叉树的输入格式。
• 指针index按顺序遍历整个数组，每个元素只会被处理一次，时间复杂度为O(n)，空间复杂度为O(n)（最坏情况是完全二叉树，队列最多存储n/2个节点）。

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