在Python中编写程序以检查两个叶子的节点序列是否相同

叶子节点是指二叉树中没有子节点的节点，一个二叉树的叶子节点序列是指从根节点开始到叶子节点结束的节点路径，不包含非叶子节点。假设我们有两个二叉树A和B，如何判断它们的叶子节点序列是否相同呢？

更多Python相关文章，请阅读：Python 教程

算法思路

我们可以先用先序遍历得到每个二叉树的叶子节点序列，然后将两个序列进行比较，如果相同则说明两个二叉树的叶子节点序列相同，否则不相同。先给出二叉树的基本结构定义。

class Node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None
        self.right_child = None

class BinaryTree:
    def __init__(self):
        self.root = None

接下来，我们需要实现先序遍历算法得到叶子节点序列，代码如下：

def preorder_traversal(root: Node, lst: list):
    if root:
        # 如果当前节点没有左右子树说明它是一个叶子节点
        if not root.left_child and not root.right_child:
            lst.append(root)
        preorder_traversal(root.left_child, lst)
        preorder_traversal(root.right_child, lst)

# 获取二叉树的叶子节点序列
def get_leaf_nodes(root: Node):
    leaf_lst = []
    preorder_traversal(root, leaf_lst)
    leaf_value_lst = [node.value for node in leaf_lst]
    return leaf_value_lst

下面是我们用这个算法获取两个二叉树A和B的叶子节点序列的代码。

# 创建两个二叉树
a = BinaryTree()
b = BinaryTree()
a.root = Node(1)
a.root.left_child = Node(2)
a.root.right_child = Node(3)
a.root.left_child.left_child = Node(4)
a.root.left_child.right_child = Node(5)
a.root.right_child.left_child = Node(6)
a.root.right_child.right_child = Node(7)
b.root = Node(1)
b.root.left_child = Node(2)
b.root.right_child = Node(3)
b.root.left_child.left_child = Node(4)
b.root.left_child.right_child = Node(5)
b.root.right_child.left_child = Node(6)
b.root.right_child.right_child = Node(8)

# 获取叶子节点序列
a_leaf = get_leaf_nodes(a.root)
b_leaf = get_leaf_nodes(b.root)

# 比较两个叶子节点序列是否相同
if a_leaf == b_leaf:
    print("两个二叉树的叶子节点序列相同")
else:
    print("两个二叉树的叶子节点序列不相同")

运行结果为：

两个二叉树的叶子节点序列不相同

结论

通过先序遍历算法，我们可以实现一个简单的二叉树叶子节点序列比较程序，该算法可以应用于判断两个二叉树叶子节点序列是否相同。