Pythonを使用して適切なリーフノードペアの数を見つけるプログラム

二分木があるとします。および別の値の距離d。 2つの異なるリーフノードのペアは、これら2つのノード間の最短経路が距離dよりも小さいか、同じである場合に適切であると言われます。

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

距離d=4の場合、パスの長さの距離が2であるため、ペアは（8,7）と（5,6）ですが、（7,5）または（8,6）または他のペアであるため、出力は2になります。パスの長さが5であり、d=4よりも大きいため適切ではありません

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

• sol：=0

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

• ルートがnullの場合、

  • 新しいリストを返す

• 根が葉の場合

  • 1つのペアを持つ配列を返します[0、0]

• それ以外の場合

  • cur：=新しいリスト

  • l：=util（ルートの左側）

  • r：=util（ルートの権利）

  • lのnごとに、実行します

    • n [1]：=n [1] + 1

  • rのnごとに、実行します

    • n [1]：=n [1] + 1

  • rのnごとに、実行します

    • lのn1ごとに、実行します

      • n [1] + n1 [1] <=dの場合、

        • sol：=sol + 1

  • l+rを返す

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

• util（root）

• solを返す

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

例

class TreeNode:
def __init__(self, val=0, left=None, right=None):
   self.val = val
   self.left = left
   self.right = right
class Solution:
   def __init__(self):
      self.sol = 0
   def solve(self, root, d):
      def util(root):
         if not root:
            return []
         if not root.left and not root.right:
            return [[0, 0]]
         else:
            cur = []
            l = util(root.left)
            r = util(root.right)
            for n in l:
               n[1] += 1
            for n in r:
               n[1] += 1
            for n in r:
               for n1 in l:
                  if n[1] + n1[1] <= d:
                     self.sol += 1
            return l+r
      util(root)
      return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))

入力

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4

出力

2