如何用字典非递归创建二叉树？附Node类及尝试代码

首先，我们来修正你的实现思路，解决几个核心问题，然后给出完整的可运行代码。

你的代码存在的几个问题： #

1. 节点重复创建：每次循环都新建Node实例，没有复用已创建的节点（比如父节点2的子节点4，后续处理4时又新建了一个独立的4节点，导致树的关联断裂）。
2. Node初始化错误：你的Node类的__init__只接受key参数，left和right是实例属性需要后续赋值，但你直接在初始化时传入子节点，会导致参数不匹配报错。
3. 根节点未正确处理：你提到found_root但没有实现正确的根节点查找逻辑，二叉树的根是唯一没有父节点的节点，需要从字典中推导出来。
4. 循环逻辑错误：while (p != len(parents)-1)会漏掉最后一个节点，正确的遍历应该覆盖所有父节点。

正确的迭代实现方案 #

我们可以用节点映射表来避免重复创建节点，先完成所有节点的实例化，再逐个关联父子关系，步骤如下：

1. 找到根节点：根节点是所有键中，没有出现在任何子节点位置的那个（因为二叉树的根没有父节点）。
2. 创建节点映射：用字典存储每个键对应的Node实例，方便快速查找复用。
3. 关联左右子节点：遍历原字典，将每个父节点的left和right属性指向对应的子节点实例（如果子节点不为None）。

完整代码：

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def build_binary_tree(dictionary):
    # 步骤1：找到根节点
    child_nodes = set()
    for left, right in dictionary.values():
        if left is not None:
            child_nodes.add(left)
        if right is not None:
            child_nodes.add(right)
    # 根节点是不在子节点集合中的键
    root_key = next(key for key in dictionary.keys() if key not in child_nodes)
    
    # 步骤2：创建所有节点的映射表，避免重复创建
    node_map = {key: Node(key) for key in dictionary.keys()}
    
    # 步骤3：关联每个父节点的左右子节点
    for parent_key, (left_key, right_key) in dictionary.items():
        parent_node = node_map[parent_key]
        if left_key is not None:
            parent_node.left = node_map[left_key]
        if right_key is not None:
            parent_node.right = node_map[right_key]
    
    # 返回根节点
    return node_map[root_key]

# 测试用例
test_dict = {1:(2,3), 2:(4,5), 4:(6, None), 3:(7,8), 5:(None, None), 6:(None, None),7:(None, None),8:(None, None)}
root = build_binary_tree(test_dict)
# 验证：根节点是1，左子节点是2，2的左子节点是4，4的左子节点是6
print(root.val)  # 输出1
print(root.left.val)  # 输出2
print(root.left.left.val)  # 输出4
print(root.left.left.left.val)  # 输出6

代码说明 #

• 节点映射表node_map：确保每个键只对应一个Node实例，解决了重复创建节点的问题。
• 根节点查找：通过集合存储所有子节点，快速筛选出没有父节点的根。
• 迭代关联：全程没有递归，通过遍历字典完成所有节点的关联，逻辑清晰且高效。

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