Python 中检查两棵二叉树的叶子遍历是否相同

假设我们有两棵二叉树。我们需要检查这两棵树的叶子遍历是否相同。众所周知，叶子遍历是从左到右遍历叶子的序列。

因此，如果输入如下所示：

则输出将为 True，因为两棵树的左侧遍历序列相同，即 [5, 7, 8]。

为了解决这个问题，我们将遵循以下步骤：

• s1 := 一个新的列表，s2 := 另一个新的列表
• 将 r1 插入 s1，将 r2 插入 s2
• 当 s1 和 s2 不为空时，执行以下操作：
  • 如果 s1 为空或 s2 为空，则
    • 返回 False
  • r1_node := s1 的最后一个节点，并将其从 s1 中删除
  • 当 r1_node 不等于 null 且 r1_node 不是叶子节点时，执行以下操作：
    • 如果 r1_node 的右子节点不等于 null，则
      • 将 r1_node 的右子节点插入 s1 的末尾
    • 如果 r1_node 的左子节点不等于 null，则
      • 将 r1_node 的左子节点插入 s1 的末尾
      • r1_node := s1 的最后一个节点，并将其从 s1 中删除
  • r2_node := s2 的最后一个节点，并将其从 s2 中删除
  • 当 r2_node 不等于 null 且 r2_node 不是叶子节点时，执行以下操作：
    • 如果 r2_node 的右子节点不等于 null，则
      • 将 r2_node 的右子节点插入 s2 的末尾
    • 如果 r2_node 的左子节点不等于 null，则
      • 将 r2_node 的左子节点插入 s2 的末尾
    • r2_node := s2 的最后一个节点，并将其从 s2 中删除
  • 如果 r1_node 为 null 且 r2_node 不为 null，则
    • 返回 False
  • 如果 r1_node 不为 null 且 r2_node 为 null，则
    • 返回 False
  • 如果 r1_node 和 r2_node 均不为 null，则
    • 如果 r1_node 的值不等于 r2_node 的值，则
      • 返回 False
• 返回 True

示例

让我们看一下以下实现，以便更好地理解：

 在线演示

class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = self.right = None
   def is_leaf(self):
      return self.left == None and self.right == None
def solve(r1, r2):
   s1 = []
   s2 = []
   s1.append(r1)
   s2.append(r2)
   while len(s1) != 0 or len(s2) != 0:
      if len(s1) == 0 or len(s2) == 0:
         return False
      r1_node = s1.pop(-1)
      while r1_node != None and not r1_node.is_leaf():
         if r1_node.right != None:
            s1.append(r1_node.right)
         if r1_node.left != None:
            s1.append(r1_node.left)
            r1_node = s1.pop(-1)
      r2_node = s2.pop(-1)
      while r2_node != None and not r2_node.is_leaf():
         if r2_node.right != None:
            s2.append(r2_node.right)
         if r2_node.left != None:
            s2.append(r2_node.left)
         r2_node = s2.pop(-1)
      if r1_node == None and r2_node != None:
         return False
      if r1_node != None and r2_node == None:
   return False
if r1_node != None and r2_node != None:
if r1_node.val != r2_node.val:
return False
return True
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

输入

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

输出

True

Arnab Chakraborty

更新于: 2021年1月19日

115 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习