在Python中查找具有偶数总和的最长路径的程序

假设我们有一棵二叉树。我们必须找到总和为偶数的最长路径的长度。

因此，如果输入如图像，则输出将为5，因为路径如[5, 2, 4, 8, 5]，总和= 24（偶数）。

为了解决这个问题，我们将按照以下步骤进行 −

定义一个函数dfs()。这将取节点
如果节点为空，则
- 返回一对（0, -inf）
（左0，左1）：= dfs（节点的左侧）
（右0，右1）：= dfs（节点的右侧）
如果节点的值为奇数，则
- ans：= ans，（left1 + right0 + 1）和（left0 + right1 + 1）的最大值
- 返回一对（（left1 + 1）的最大值，（right1 + 1）和0的最大值），（（left0 + 1）和（right0 + 1）的最大值）
否则，
- ans：= ans，（left0 + right0 + 1）和（left1 + right1 + 1）的最大值
- 返回一对（（left0 + 1）的最大值，（right0 + 1）和0的最大值），（（left1 + 1）和（right1 + 1）的最大值）
从main方法执行以下操作−
ans：= 0
dfs（root）
返回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)