Pythonで二分木の最長交互パスの長さを見つけるプログラム

二分木があるとすると、左と右の子を交互に繰り返して下る最長のパスを見つける必要があります。

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

交互のパスが[2、4、5、7、8]であるため、出力は5になります。

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

• rootがnullの場合、
  • 0を返す
• 関数dfs（）を定義します。これには、ノード、カウント、フラグが必要です
• ノードがnullでない場合、
  • フラグがTrueと同じ場合、
    • a：=dfs（ノードの左側、カウント+ 1、False）
    • b：=dfs（ノードの右側、1、True）
  • それ以外の場合、フラグがFalseと同じ場合、
    • a：=dfs（ノードの右、カウント+ 1、True）
    • b：=dfs（ノードの左側、1、False）
  • a、bの最大値を返す
• 返品数
• メインの方法から次の手順を実行します。
• a：=dfs（ルートの左側、1、False）
• b：=dfs（ルートの右、1、True）
• a、bの最大値を返す

理解を深めるために、次の実装を見てみましょう。

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if not root:
         return 0

      def dfs(node, count, flag):
         if node:
            if flag == True:
               a = dfs(node.left, count + 1, False)
               b = dfs(node.right, 1, True)
            elif flag == False:
               a = dfs(node.right, count + 1, True)
               b = dfs(node.left, 1, False)

            return max(a, b)
      return count

      a = dfs(root.left, 1, False)
      b = dfs(root.right, 1, True)

   return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)

出力

5