Pythonの二分木で対角パス要素のそれぞれの合計を見つけるプログラム

二分木があるとすると、ツリーの各対角線の合計を右上から右下に向かって見つける必要があります。

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

対角線が[12,15]、[8,10]、[3]であるため、出力は[27、18、3]になります。したがって、合計値は[27、18、3]

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

関数traverse（）を定義します。これは、ノード、numLeft、出力を取ります

• ノードがnullの場合、

  • 戻る

• numLeft> =出力のサイズの場合、

  • 出力の最後にノードのデータを挿入

• それ以外の場合

  • output [numLeft]：=output[numLeft]+ノードのデータ

• ノードの左側がnullでない場合、

  • トラバース（ノードの左側、numLeft + 1、出力）

• ノードの権利がnullでない場合、

  • トラバース（ノードの右側、numLeft、出力）

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

• 出力：=新しいリスト

• traverse（root、0、output）

• 出力を返す

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

例

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):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

入力

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)

出力

[27, 18, 3]