Python 中根到叶路径中的节点不足

pythonserver side programmingprogramming更新于 2025/8/25 5:32:17

假设我们有一棵二叉树。如果与该节点相交的每条这样的根到叶路径的总和都严格小于限制,则该节点被称为不足节点。我们必须同时删除所有不足节点,并返回结果二叉树的根。因此,如果树是这样的,并且限制是 1 −

那么输出树将是 −

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个方法solve(),它将获取根并限制
  • 如果节点没有左子树和右子树,那么
    • 如果 root 的值小于 1,则返回 null,否则返回 root
  • 如果 root 有左子树,则 root 的左侧 := resolve(root 的左侧,limit – root 的值)
  • 如果 root 有右子树,则 root 的右侧 := resolve(root 的右侧,limit – root 的值)
  • 如果 root 有左子树、右子树或两者,则返回 root,否则返回 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]

相关文章


有用资源