파이썬의 이진 트리에서 두 번째로 깊은 노드를 찾는 프로그램

<시간/>

이진 트리가 있다고 가정합니다. 우리는 두 번째로 깊은 잎사귀의 깊이를 찾아야 합니다. 가장 깊은 리프가 여러 개 있는 경우 두 번째로 깊은 리프 노드가 다음으로 높은 노드가 됩니다. 우리가 알고 있듯이 루트의 깊이는 0입니다.

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

두 번째로 깊은 노드가 3이므로 출력은 1이 됩니다.

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

루트가 null이면
- null 반환
노드:=새 목록
노드 끝에 루트 삽입
count :=0, 이전 :=0, 현재 :=0
노드가 비어 있지 않은 동안 수행
- new :=새 목록
- 플래그 :=참
- 노드의 각 노드에 대해 다음을 수행합니다.
  - 플래그가 true이고 (노드의 왼쪽이 null인 경우) 및 (노드의 오른쪽이 null인 경우),
    - 이전 :=지금
    - 지금 :=카운트
    - 플래그 :=거짓
  - 노드의 왼쪽이 null이 아니면
    - 새 노드 끝에 노드 왼쪽 삽입
  - 노드의 권한이 null이 아니면
    - 새 항목 끝에 노드 오른쪽 삽입
- 노드:=신규
- 카운트 :=카운트 + 1
이전 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예

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

class Solution:
   def solve(self, root):
      if root is None:
         return None
      nodes = []
      nodes.append(root)
      count = 0
      prev = 0
      now = 0
      while nodes:
         new = []
         flag = True
         for node in nodes:
         if flag and (not node.left) and (not node.right):
            prev = now
            now = count
            flag = False
         if node.left:
            new.append(node.left)
         if node.right:
            new.append(node.right)
      nodes = new
      count += 1
   return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

입력

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)