Python程式：查詢樹中所有非相鄰節點的最大和

假設我們有一個二叉樹，我們需要找到可以獲得的最大值之和，前提是不能有兩個值是相鄰的（父節點和子節點）。

因此，如果輸入類似於

則輸出將為 17，因為 10、4、3 不相鄰。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 f()。它將接收節點作為引數。
  • 如果節點為空，則
    • 返回 (0, 0)
  • (a, b) := f(節點的左子節點)
  • (c, d) := f(節點的右子節點)
  • 返回一個對 (節點值 + b + d 與 a + c 的最大值, a + c)
  • 從主方法中呼叫 f(根節點) 並返回其第一個值。

讓我們看看以下實現以更好地理解：

示例

 即時演示

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.val = data
   self.left = left
   self.right = right
def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c
class Solution:
   def solve(self, root):
      return f(root)[0]
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))

輸入

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)

輸出

17

更新於: 2020年10月19日

260 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告