Python程式：查詢二叉樹中最長偶數路徑

假設我們有一個二叉樹，我們需要找到樹中任意兩個節點之間由偶數值組成的最長路徑。

因此，如果輸入類似於

則輸出將為 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 的最大值

    • 返回 (-1, -1)

  • 在主方法中執行以下操作：

  • find(根節點)

  • 返回 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)

輸出

5

更新於： 2020年10月10日

155 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告