17 树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）

示例：

树A:     3
        / \
       4   5
      / \
     1   2

树B:   4
      /
     1

输出: True

解题思路

核心思想：分两步：

1. 在树A中找到与树B根节点值相同的节点
2. 从该节点开始，判断树B是否是树A的子结构

关键步骤：

1. 如果树B为空，返回True（空树是任何树的子结构）
2. 如果树A为空，返回False
3. 如果当前节点的值相等，检查是否匹配
4. 如果不匹配，递归检查左子树和右子树

时间复杂度：O(m*n)，m为A的节点数，n为B的节点数 空间复杂度：O(m)

Python 实现

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


def has_subtree(a, b):
    """
    判断B是否是A的子结构

    Args:
        a: 树A的根节点
        b: 树B的根节点

    Returns:
        bool: B是否是A的子结构
    """
    if not a or not b:
        return False

    # 检查当前节点是否匹配，或者递归检查左右子树
    return does_tree1_has_tree2(a, b) or has_subtree(a.left, b) or has_subtree(a.right, b)


def does_tree1_has_tree2(a, b):
    """
    判断从a开始的子树是否完全包含b
    """
    # B已经遍历完，匹配成功
    if not b:
        return True
    # A遍历完但B没完，匹配失败
    if not a:
        return False
    # 节点值不匹配
    if a.val != b.val:
        return False

    # 递归检查左右子树
    return does_tree1_has_tree2(a.left, b.left) and does_tree1_has_tree2(a.right, b.right)


# 辅助函数：创建树
def build_tree(values, index=0):
    if index >= len(values) or values[index] is None:
        return None
    node = TreeNode(values[index])
    node.left = build_tree(values, 2 * index + 1)
    node.right = build_tree(values, 2 * index + 2)
    return node


# 测试代码
if __name__ == "__main__":
    # 树A
    a_values = [3, 4, 5, 1, 2]
    a = build_tree(a_values)

    # 树B
    b_values = [4, 1]
    b = build_tree(b_values)

    print(f"树B是否是树A的子结构: {has_subtree(a, b)}")  # True

    # 测试不匹配的情况
    b2 = build_tree([4, 2])
    print(f"树B2是否是树A的子结构: {has_subtree(a, b2)}")  # False

# 输出:
# 树B是否是树A的子结构: True
# 树B2是否是树A的子结构: False

图解

示例:
树A:       树B:
    3         4
   / \       /
  4   5     1
 / \
1   2

匹配过程:
1. 在树A中找值为4的节点，找到节点A1
2. 从A1开始检查:
   - A1.val == B.root.val ✓
   - A1.left.val == B.left.val (1 == 1) ✓
   - B没有右子树，跳过
   - 匹配成功

如果树B是:
    4
   /
  2

匹配过程:
1. 在树A中找值为4的节点，找到节点A1
2. 从A1开始检查:
   - A1.val == B.root.val ✓
   - A1.left.val != B.left.val (1 != 2) ✗
   - 匹配失败
3. 继续找树A中其他值为4的节点（没有），返回False