資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢二叉樹中和為偶數的最長路徑長度
假設我們有一棵二叉樹。我們需要找到和為偶數的最長路徑的長度。
因此，如果輸入類似於圖片，則輸出將為 5，因為路徑為 [5, 2, 4, 8, 5]，和為 24（偶數）。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 dfs()。它將接收節點作為引數。
- 如果節點為空，則
- 返回一個對 (0, -inf)
- (left_0, left_1) := dfs(節點的左子節點)
- (right_0, right_1) := dfs(節點的右子節點)
- 如果節點的值為奇數，則
- ans := ans，(left_1 + right_0 + 1) 和 (left_0 + right_1 + 1) 中的最大值
- 返回一個對 ( (left_1 + 1)，(right_1 + 1) 和 0 中的最大值 ， (left_0 + 1) 和 (right_0 + 1) 中的最大值)
- 否則，
- ans := ans，(left_0 + right_0 + 1) 和 (left_1 + right_1 + 1) 中的最大值
- 返回一個對 ( (left_0 + 1)，(right_0 + 1)，0 中的最大值 ， (left_1 + 1)，(right_1 + 1) 中的最大值)
- 從主方法執行以下操作：
- ans := 0
- dfs(根節點)
- 返回 ans
示例（Python）
讓我們看看以下實現以更好地理解：
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):
def dfs(node):
if not node:
return 0, float("-inf")
left_0, left_1 = dfs(node.left)
right_0, right_1 = dfs(node.right)
if node.val & 1:
self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
else:
self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
self.ans = 0
dfs(root)
return self.ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)
print(ob.solve(root))輸入
root = TreeNode(2) root.left = TreeNode(5) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(5)
輸出
5
更新於： 2020年12月12日
146 次檢視
廣告