Pythonでツリーの左端の最深ノードを見つけるプログラム

二分木があるとしましょう。最も深いノードの値を見つける必要があります。最も深いノードが複数ある場合は、左端の最も深いノードを返します。

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

4と7が最も深いが、4が最も残っているため、出力は4になります。

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

• queue：=1つのノードルートを持つキュー。

• left_max：=ルートの値

• キューのサイズが0より大きい場合は、実行してください

  • level_size：=キューのサイズ

  • 0からlevel_sizeの範囲のiの場合、実行

    • temp：=キューの最初の要素を削除します

    • iが0と同じ場合、

      • left_max：=温度の値

    • 温度の左側がゼロ以外の場合、

      • キューの最後に一時の左側を挿入します

    • 臨時雇用者の権利がnullでない場合、

      • キューの最後に一時の権利を挿入します

  • left_maxを返す

理解を深めるために、次の実装を見てみましょう-

例

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

class Solution:
   def solve(self, root):
      queue = [root]
      left_max = root.val
      while len(queue) > 0:
         level_size = len(queue)
         for i in range(level_size):
            temp = queue.pop(0)
            if i == 0:
               left_max = temp.val
            if temp.left:
               queue.append(temp.left)
            if temp.right:
               queue.append(temp.right)
      return left_max
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

4