Pythonで二分木の最大幅を見つけるプログラム

二分木があるとすると、ツリー内の任意のレベルの最大幅を見つける必要があります。ここで、レベルの幅は、左端のノードと右端のノードの間に保持できるノードの数です。

したがって、入力が

その場合、出力は2になります

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

• マップdを作成し、最小値と最大値を保持するには、最小値は最初は無限大で、最大値は0です

• 関数dfs（）を定義します。これはルートを取ります、pos：=0、depth：=0

• ルートがnullの場合、戻り値はありません

• d [depth、0] =d [depth、0]とposの最小値

• d [depth、1] =d [depth、1]とposの最大値

• dfs（ノードの左側、2 * pos、depth + 1）

• dfs（ノードの右側、2 * pos + 1、depth + 1）

• メインの方法から、次のようにします-

• dfs（root）

• mx：=0

• dのすべての値のリストにある各最小-最大ペアについて、実行します

  • 左：=最小、右：=最大

  • mx：=mxの最大値、right-lelf + 1

• mxを返す

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

例

from collections import defaultdict
   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):
   d=defaultdict(lambda: [1e9,0])
   def dfs(node, pos=0, depth=0):
      if not node:
         return
      d[depth][0]=min(d[depth][0],pos)
      d[depth][1]=max(d[depth][1],pos)
      dfs(node.left,2*pos,depth+1)
      dfs(node.right,2*pos+1,depth+1)
   dfs(root)
   mx=0
   for interval in d.values():
      l,r=interval
      mx=max(mx,r-l+1)
   return mx

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

出力

2