Pythonのルートからリーフへのパスのノードが不十分です

二分木があるとします。このノードと交差するそのようなすべてのルートからリーフへのパスの合計が厳密に制限未満である場合、そのノードは不十分であると呼ばれます。不十分なノードをすべて同時に削除し、結果の二分木のルートを返す必要があります。したがって、ツリーがのようで、制限が1 −

その場合、出力ツリーは-

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

• メソッドsolve（）を定義します。これはルートを取り、制限します
• ノードに左右のサブツリーがない場合は、
  • rootの値が1未満の場合はnullを返し、そうでない場合はroot
• ルートがサブツリーを離れている場合、ルートの左側：=resolve（ルートの左側、制限–ルートの値）
• ルートに右のサブツリーがある場合、ルートの右：=solve（ルートの右、制限–ルートの値）
• ルートに左サブツリーまたは右サブツリー、あるいはその両方がある場合は、ルートを返します。それ以外の場合はnullを返します。

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

例

class Solution(object):
   def sufficientSubset(self, root, limit):
      """
      :type root: TreeNode
      :type limit: int
      :rtype: TreeNode
      """
      if not root.left and not root.right:
         return None if root.val<limit else root
      if root.left:
         root.left= self.sufficientSubset(root.left,limit-root.val)
      if root.right:
         root.right = self.sufficientSubset(root.right,limit-root.val)
      return root if root.left or root.right else None

入力

[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]
1

出力

[1,2,3,4,null,null,7,8,9,null,14]