用Python查找好的叶节点对数的程序

假设我们有一棵二叉树，还有一个值距离d。两个不同叶节点的一对称为好的叶节点，当这两个节点之间的最短路径小于或等于距离d时。

因此，如果输入如下：

用Python查找好的叶节点对数的程序

并且距离d = 4，则输出将为2，因为叶节点对为(8,7)和(5,6)，因为它们的路径长度距离为2，但(7,5)或(8,6)或其他叶节点对不好，因为它们的路径长度为5，大于d = 4。

为了解决这个问题，我们将按照以下步骤进行 –

sol：= 0
定义一个函数util()。这将取root
如果root为null，则
- 返回一个新列表
如果root是叶节点，则
- 返回一个含有一个pair [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