資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究Python程式：計算路徑和為k的路徑數量
假設我們有一棵二叉樹和另一個值 k，我們需要找到從根節點到葉節點的、和為 k 的唯一路徑的數量。
例如，如果輸入是：
並且 k = 5，則輸出為 2，因為路徑為 [2, 3] 和 [1, 4]
為了解決這個問題，我們將遵循以下步驟：
- count := 一個字典，初始值為鍵 0，值為 1
- ans := 0，prefix := 0
- 定義一個函式 dfs()。它將接收節點作為引數。
- 如果節點不為空，則：
- prefix := prefix + 節點的值
- ans := ans + (count[prefix - target]，如果不存在則為 0)
- count[prefix] := count[prefix] + 1
- dfs(節點的左子節點)
- dfs(節點的右子節點)
- count[prefix] := count[prefix] - 1
- prefix := prefix - 節點的值
- 在主方法中，執行以下操作：
- dfs(根節點)
- 返回 ans
讓我們來看下面的實現，以便更好地理解：
示例
from collections import Counter class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root, target): count = Counter([0]) ans = prefix = 0 def dfs(node): nonlocal ans, prefix if node: prefix += node.val ans += count[prefix - target] count[prefix] += 1 dfs(node.left) dfs(node.right) count[prefix] -= 1 prefix -= node.val dfs(root) return ans ob = Solution() root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(1) root.right.left.right = TreeNode(2) k = 5 print(ob.solve(root, k))
輸入
root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(1) root.right.left.right = TreeNode(2) 5
輸出
2
更新於：2020年12月2日
瀏覽量：140
廣告