基于DFS数组构建完美二叉树：递归/非递归实现方案探讨

嘿，这个问题其实比你想的要好办——因为完美二叉树的结构是固定的，我们完全可以利用它的节点数量规律来递归拆分左右子树，根本不用额外判断叶子节点！先给你理清楚核心逻辑，再上递归和非递归的代码实现～

核心思路：靠完美二叉树的“固定结构”破局 #

首先得明确完美二叉树的关键特性：

• 深度为depth的完美二叉树，总节点数是 2^depth - 1
• 任意一个非叶子节点的子树，如果深度是k，那么它的左、右子树深度都是k-1，每个子树的节点数都是 2^(k-1)-1

而你给出的DFS数组明显是前序遍历的结果（根→左子树→右子树），所以对于当前子树的节点数组：

1. 第一个元素必然是根节点
2. 接下来的2^(k-1)-1个元素是左子树的前序遍历结果
3. 剩下的2^(k-1)-1个元素是右子树的前序遍历结果

这里的k就是当前子树的深度：当k=1时，这就是叶子节点，直接返回即可；当k>1时，必然是非叶子节点，一定有左右子树。完美解决了你担心的“不知道叶子/非叶子”的问题！

递归实现（最直观） #

先定义二叉树节点类，再写递归构建函数：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_perfect_bt(depth, dfs_array):
    # 递归终止条件：深度为1，直接返回叶子节点
    if depth == 1:
        return TreeNode(dfs_array[0])
    
    # 计算左子树的节点数量：用位运算等价于2^(depth-1)-1，比pow()更快
    left_subtree_size = (1 << (depth - 1)) - 1
    
    # 构建根节点
    root = TreeNode(dfs_array[0])
    # 递归构建左子树：取数组[1 : 1+left_subtree_size]的部分，深度减1
    root.left = build_perfect_bt(depth - 1, dfs_array[1 : 1 + left_subtree_size])
    # 递归构建右子树：取数组剩下的部分，深度减1
    root.right = build_perfect_bt(depth - 1, dfs_array[1 + left_subtree_size : ])
    
    return root

测试示例 #

用你给出的输入测试：

# 示例输入
depth = 4
dfs_array = [0,1,3,7,8,4,9,10,2,5,11,12,6,13,14]
# 构建树
root = build_perfect_bt(depth, dfs_array)

你可以写个前序遍历函数验证结果是否和输入数组一致，比如：

def preorder_traversal(root):
    res = []
    def traverse(node):
        if not node:
            return
        res.append(node.val)
        traverse(node.left)
        traverse(node.right)
    traverse(root)
    return res

print(preorder_traversal(root))  # 输出和输入dfs_array完全一致

非递归实现（迭代法） #

如果不想用递归，可以用栈模拟递归过程。栈里存储的是待构建子树的信息：子树深度、数组的起始/结束索引、父节点、以及当前是父节点的左/右孩子。

代码实现 #

def build_perfect_bt_iterative(depth, dfs_array):
    if not dfs_array:
        return None
    
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    root = None
    # 栈元素格式：(子树深度, 数组起始索引, 数组结束索引, 父节点, 是否是左孩子)
    stack = [(depth, 0, len(dfs_array)-1, None, None)]
    
    while stack:
        current_depth, start_idx, end_idx, parent, is_left_child = stack.pop()
        
        # 创建当前节点
        current_node = TreeNode(dfs_array[start_idx])
        # 把当前节点挂到父节点的对应位置
        if parent:
            if is_left_child:
                parent.left = current_node
            else:
                parent.right = current_node
        else:
            # 没有父节点，说明是根节点
            root = current_node
        
        # 如果是叶子节点（深度为1），无需处理子树
        if current_depth == 1:
            continue
        
        # 计算左子树的节点数量
        left_subtree_size = (1 << (current_depth - 1)) - 1
        # 右子树的数组范围：start_idx+1+left_subtree_size 到 end_idx
        right_start = start_idx + 1 + left_subtree_size
        right_end = end_idx
        # 先压右子树（栈是后进先出，这样左子树会先被处理，符合前序顺序）
        stack.append((current_depth - 1, right_start, right_end, current_node, False))
        
        # 左子树的数组范围：start_idx+1 到 start_idx+left_subtree_size
        left_start = start_idx + 1
        left_end = start_idx + left_subtree_size
        # 再压左子树
        stack.append((current_depth - 1, left_start, left_end, current_node, True))
    
    return root

逻辑说明 #

每次从栈里弹出一个子树任务，先创建当前节点并挂到父节点上；如果不是叶子节点，就把右子树和左子树的任务压入栈（因为栈是后进先出，所以先压右，再压左，这样弹出时会先处理左子树，和前序遍历的顺序一致）。

同样用之前的示例测试，结果和递归版本完全相同。

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