葉を除く各ノードの値がPythonでその子の値の合計であるかどうかを確認するプログラム

二分木があるとすると、葉を除くツリー内のすべてのノードについて、その値が左の子の値と右の子の値の合計と同じであるかどうかを確認する必要があります。

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

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

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

• 関数dfs（）を定義します。これが定着します

• ルートがnullの場合、

  • Trueを返す

• ルートの左側がnullで、ルートの右側がnullの場合、

  • Trueを返す

• 左：=0

• ルートの左側がnullでない場合、

  • left：=ルートの左側の値

• 右：=0

• ルートの権利がnullでない場合、

  • right：=ルートの権利の値

• （左+右がルートの値と同じ）でdfs（ルートの左）がtrueで、dfs（ルートの右）がtrueの場合にtrueを返します

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

• dfs（root）を返す

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

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      def dfs(root):
         if root == None:
            return True
         if root.left == None and root.right == None:
            return True
         left = 0
         if root.left:
            left = root.left.val
         right = 0
         if root.right:
            right = root.right.val
         return (left + right == root.val) and dfs(root.left) and
      dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))

入力

root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10)
root.left.left = TreeNode(3) root.left.right = TreeNode(5)

出力

True