Pythonで二分木の最長の偶数値パスを見つけるプログラム

二分木があるとすると、ツリー内の任意の2つのノード間の偶数の値で構成される最長のパスを見つける必要があります。

したがって、入力が次のような場合

最長のパスが[10、2、4、8、6]であるため、出力は5になります。

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

• ans：=0

• 関数find（）を定義します。これはノードを取ります

• ノードがnullの場合、

  • 戻り値（-1、-1）

• leftCnt：=find（ノードの左側）の戻り値の最大値+ 1

• rightCnt：=find（ノードの右側）の戻り値の最大値+ 1

• ノードの値が偶数の場合、

  • ans：=ansの最大値と（leftCnt + rightCnt + 1）

  • return（leftCnt、rightCnt）

• それ以外の場合

  • ans：=ans、leftCnt、rightCntの最大値

  • 戻り値（-1、-1）

• メインの方法から、次のようにします-

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

出力

5