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

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

则输出树将变为 −

为了解决此问题，我们将执行以下步骤 −

  • 定义 solve() 方法，该方法将采用 root 和 limit
  • 如果节点没有左子树和右子树，则
    • 如果 root 的值小于 1，则返回 null，否则返回 root
  • 如果 root 有左子树，则 root 的左侧 := solve(root 的左侧, limit – root 的值)
  • 如果 root 有右子树，则 root 的右侧 := solve(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]

更新时间：05-03-2020

208 次浏览

开启你的 事业

完成课程即可获得认证

开始学习
广告