用 Python 编写程序查找二叉树的最长偶值路径

pythonserver side programmingprogramming更新于 2026/1/23 22:04:17

假设我们有一棵二叉树，我们必须找到树中任意两个节点之间由偶值组成的最长路径。

因此，如果输入如下

那么输出将是 5，因为最长路径是 [10, 2, 4, 8, 6]。

为了解决这个问题，我们将遵循以下步骤 −

ans := 0
定义一个函数 find() 。这将获取节点
如果节点为空，则
- 返回 (-1, -1)
leftCnt := find(节点左侧) 返回值的最大值 + 1
rightCnt := find(节点右侧) 返回值的最大值 + 1
如果节点值为偶数，则
- ans := ans 和 (leftCnt + rightCnt + 1) 的最大值
- 返回 (leftCnt, rightCnt)
否则，
- ans := ans、leftCnt 和rightCnt
- return (-1, -1)
从 main 方法执行以下操作 −
find(root)
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

输入

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)