如何判断给定的多叉树是否为另一棵多叉树的子结构

核心定义 #

首先明确子结构的含义：存在A中的某个节点，从该节点出发，其节点值、层级结构与B完全一致——B的每个节点都能在A的对应位置找到匹配的节点（值相等），且B的所有子节点都能对应A中该节点的子节点部分（注意：子结构≠子树，子树要求包含节点的所有后代，而子结构只要求匹配B的完整结构）。

解决思路 #

分两步处理：

1. 匹配检查：写一个递归函数，判断以A中某个节点为根的子树是否和B完全匹配。
2. 遍历搜索：遍历A的所有节点，对每个节点调用匹配检查函数，只要有一个节点匹配成功，就说明B是A的子结构。

代码实现（有序多叉树） #

假设多叉树节点结构如下：

class TreeNode:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

1. 匹配检查函数

判断两个节点为根的树是否结构和值完全匹配（子节点顺序一致）：

def is_match(node_a, node_b):
    # B的当前节点为空，说明这部分匹配完成
    if not node_b:
        return True
    # A的当前节点为空但B不为空，匹配失败
    if not node_a:
        return False
    # 节点值不相等，直接失败
    if node_a.val != node_b.val:
        return False
    # 子节点数量不一致，结构不匹配
    if len(node_a.children) != len(node_b.children):
        return False
    # 逐个递归匹配子节点
    for child_a, child_b in zip(node_a.children, node_b.children):
        if not is_match(child_a, child_b):
            return False
    return True

2. 主搜索函数

遍历A的所有节点，寻找是否存在匹配的子结构：

def has_substructure(root_a, root_b):
    # 边界情况：空树是任何树的子结构
    if not root_b:
        return True
    # A为空但B不为空，不可能匹配
    if not root_a:
        return False
    # 先检查当前节点是否匹配
    if is_match(root_a, root_b):
        return True
    # 递归检查A的所有子节点
    for child in root_a.children:
        if has_substructure(child, root_b):
            return True
    # 所有节点都不匹配
    return False

无序多叉树的适配 #

如果多叉树的子节点顺序不影响匹配（即子节点的排列顺序无关），需要修改匹配函数，确保B的每个子节点都能在A的子节点中找到唯一匹配：

def is_match_unordered(node_a, node_b):
    if not node_b:
        return True
    if not node_a or node_a.val != node_b.val:
        return False
    # 复制A的子节点列表，避免修改原数据
    available_children = node_a.children.copy()
    for child_b in node_b.children:
        matched = False
        for idx, child_a in enumerate(available_children):
            if is_match_unordered(child_a, child_b):
                # 匹配成功后移除该子节点，防止重复匹配
                available_children.pop(idx)
                matched = True
                break
        if not matched:
            return False
    return True

此时主搜索函数只需将is_match替换为is_match_unordered即可。

注意事项 #

• 节点值比较：如果节点值是复杂对象，需要自定义相等判断逻辑，不能直接用!=。
• 空树规则：若业务中不认为空树是子结构，可修改边界条件，将if not root_b: return True改为if not root_b: return False。
• 性能优化：对于大型树，可提前剪枝（比如节点值不匹配时直接跳过该节点的子树遍历）。

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