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 次瀏覽

開啟你的 事業

完成課程即可獲得認證

開始學習
廣告