Pythonで合計が偶数の最長パスの長さを見つけるプログラム

二分木があるとします。合計が偶数である最長のパスの長さを見つける必要があります。

したがって、入力が画像のような場合、パスは[5、2、4、8、5]、合計=24（偶数）のようになるため、出力は5になります。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これはノードを取ります
• ノードがnullの場合、
  • ペアを返す（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（root）
• 回答を返す

例（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