数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告