Python算法——树的子树

Python中的树的子树判定算法详解

树的子树判定是指判断一个树是否是另一棵树的子树。在本文中，我们将深入讨论树的子树判定问题以及如何通过递归算法来解决。我们将提供Python代码实现，并详细说明算法的原理和步骤。

树的子树判定问题

给定两棵二叉树，判断其中一棵树是否是另一棵树的子树。子树的定义是在原树中任意节点与其所有后代形成的树。

递归算法求解子树判定问题

递归算法是求解子树判定问题的一种常见方法。我们可以递归地判断两个树是否相等，然后在递归地对树的左子树和右子树进行判定。

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

class Solution:
    def is_subtree(self, s, t):
        if not s:
            return False
        return self.is_same_tree(s, t) or self.is_subtree(s.left, t) or self.is_subtree(s.right, t)

    def is_same_tree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.is_same_tree(s.left, t.left) and self.is_same_tree(s.right, t.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

示例

考虑以下两棵二叉树：

# 构建树1
tree1 = TreeNode(3)
tree1.left = TreeNode(4)
tree1.right = TreeNode(5)
tree1.left.left = TreeNode(1)
tree1.left.right = TreeNode(2)

# 构建树2
tree2 = TreeNode(4)
tree2.left = TreeNode(1)
tree2.right = TreeNode(2)
1
2
3
4
5
6
7
8
9
10
11

sol = Solution()
result = sol.is_subtree(tree1, tree2)
print("树2是否是树1的子树:", result)
1
2
3

输出结果：

树2是否是树1的子树: True
1

这表示树2是树1的子树。递归算法在解决子树判定问题时具有直观且高效的特性。通过理解算法的原理和实现，您将能够更好地处理树结构问题。