Pythonのバイナリツリーで2番目に深いノードを見つけるプログラム

二分木があるとしましょう。 2番目に深い葉の深さを見つける必要があります。最も深い葉が複数ある場合、2番目に深い葉ノードが次に高い葉ノードになります。私たちが知っているように、根の深さは0です。

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

2番目に深いノードは3であるため、出力は1になります。

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

• rootがnullの場合、
  • nullを返す
• ノード：=新しいリスト
• ノードの最後にルートを挿入
• count：=0、prev：=0、now：=0
• ノードが空でない間は、
  • new：=新しいリスト
  • フラグ：=True
  • ノード内のノードごとに、
    • フラグがtrueで、（ノードの左側がnull）および（ノードの右側がnull）の場合、
      • 前：=今
      • 今：=カウント
      • フラグ：=False
    • ノードの左側がnullでない場合、
      • 新規の最後にノードの左側を挿入
    • ノードの権利がnullでない場合、
      • 新規の最後にノードの右側を挿入
  • ノード：=新規
  • count：=count + 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)

出力

1