2つの二分木のリーフトラバーサルがPythonで同じかどうかを確認します

2分木があるとします。これら2本の木の葉の走査が同じかどうかを確認する必要があります。私たちが知っているように、葉の探索は左から右に横断する葉のシーケンスです。

したがって、入力が次のような場合

両方のツリーの左走査シーケンスが同じであるため、出力はTrueになります。つまり、[5、7、8]です。

これを解決するには、次の手順に従います-

• s1：=新しいリスト、s2：=別の新しいリスト
• r1をs1に挿入し、r2をs2に挿入します
• s1とs2が空ではない場合は、
  • s1が空の場合、またはs2が空の場合、
    • Falseを返す
  • r1_node：=s1の最後のノードであり、s1から削除します
  • r1_nodeはnullと同じではなく、r1_nodeはleafではありませんが、
    • r1_nodeの権利がnullと同じでない場合、
      • s1の最後にr1_nodeの右側を挿入
    • r1_nodeの左側がnullと同じでない場合、
      • s1の最後にr1_nodeの左側を挿入
      • r1_node：=s1の最後のノードであり、s1から削除します
  • r2_node：=s2の最後のノードであり、s2から削除します
  • r2_nodeがnullでなく、r2_nodeがleafでない場合は、
    • r2_nodeの権利がnullでない場合、
      • s2の最後にr2_nodeの右側を挿入
    • r2_nodeの左側がnullでない場合、
      • s2の最後にr2_nodeの左側を挿入
    • 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