Python에서 두 이진 트리의 잎 순회가 동일한지 확인

<시간/>

두 개의 이진 트리가 있다고 가정합니다. 이 두 트리의 잎 순회가 동일한지 여부를 확인해야 합니다. 우리가 알고 있듯이 잎 순회는 왼쪽에서 오른쪽으로 순회하는 잎의 시퀀스입니다.

따라서 입력이 다음과 같으면

두 트리의 왼쪽 순회 시퀀스가 동일하므로 출력은 True, 즉 [5, 7, 8]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

s1 :=새 목록, s2 :=또 다른 새 목록
r1을 s1에 삽입하고 r2를 s2에 삽입
s1과 s2가 비어 있지 않은 동안 do
- s1이 비어 있거나 s2가 비어 있으면
  - 거짓을 반환
- r1_node :=s1의 마지막 노드, s1에서 삭제
- r1_node가 null과 같지 않고 r1_node가 리프가 아닌 동안 do
  - 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가 리프가 아닌 동안 do
  - r2_node의 권한이 null이 아니면
    - s2 끝에 r2_node 오른쪽 삽입
  - r2_node의 왼쪽이 null이 아니면
    - s2 끝에 r2_node 왼쪽 삽입
  - r2_node :=s2의 마지막 노드, s2에서 삭제
- r1_node가 null이고 r2_node가 null이 아니면
  - 거짓을 반환
- r1_node가 null이 아니고 r2_node가 null이면
  - 거짓을 반환
- r1_node와 r2_node가 모두 null이 아닌 경우
  - r1_node의 값이 r2_node의 값과 같지 않으면
    - 거짓을 반환
참 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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