Pythonでバイナリツリーの最長の連続パスの長さを見つけるプログラム

二分木があるとしましょう。二分木で最長のパスを見つける必要があります。

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

連続する最長のシーケンスが[2、3、4、5、6]であるため、出力は5になります。

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

• rootがnullの場合、
  • 0を返す
• maxPath：=0
• 関数helper（）を定義します。これはノードを取ります
• inc：=1、dec：=1
• ノードの左側がnullでない場合、
  • [left_inc、left_dec]：=ヘルパー（ノードの左側）
• それ以外の場合、
  • [left_inc、left_dec]：=[0、0]
• ノードの権利がnullでない場合、
  • [right_inc、right_dec]：=ヘルパー（ノードの右側）
• それ以外の場合、
  • [right_inc、right_dec]：=[0、0]
• ノードの左側がnullでなく、ノードの値-ノードの左側の値が1と同じ場合、
  • inc：=最大incおよび（left_inc + 1）
• それ以外の場合、ノードの左側がnullでなく、ノードの値-ノードの左側の値が-1と同じである場合、
  • dec：=decの最大値と（left_dec + 1）
• ノードの権利がnullでなく、ノードの値-ノードの権利の値が1と同じ場合、
  • inc：=最大incおよび（right_inc + 1）
• それ以外の場合、ノードの権利がnullでなく、ノードの値-ノードの権利の値が-1と同じである場合、
  • dec：=decの最大値と（right_dec + 1）
• ノードの左側がnullでなく、ノードの右側がnullでなく、ノードの左側の値-ノードの値が1であり、ノードの値-ノードの右側の値が1である場合、
  • maxPath：=maxPathの最大値と（left_dec + right_inc + 1）
• それ以外の場合、ノードノードの左側がnullでなく、ノードの右側がnullでなく、ノードの左側の値-ノードの値が-1と同じである場合、
  • maxPath：=maxPathの最大値と（left_inc + right_dec + 1）
• maxPath：=maxPath、inc、decの最大値
• return inc、dec
• メインの方法から次の手順を実行します。
• helper（root）
• maxPathを返す

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

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
     
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)

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

      def helper(node):
         inc, dec = 1, 1
         if node.left:
            left_inc, left_dec = helper(node.left)
         else:
            left_inc, left_dec = 0, 0
         if node.right:
            right_inc, right_dec = helper(node.right)
         else:
            right_inc, right_dec = 0, 0

         if node.left and node.val - node.left.val == 1:
            inc = max(inc, left_inc + 1)
         elif node.left and node.val - node.left.val == -1:
            dec = max(dec, left_dec + 1)

         if node.right and node.val - node.right.val == 1:
            inc = max(inc, right_inc + 1)
         elif node.right and node.val - node.right.val == -1:
            dec = max(dec, right_dec + 1)

         if (node.left and node.right and node.left.val - node.val == 1 and node.val - node.right.val == 1):
            self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
         elif (node.left and node.right and node.left.val - node.val == -1
            and node.val - node.right.val == -1):
            self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
           
         self.maxPath = max(self.maxPath, inc, dec)
         return inc, dec

      helper(root)
      return self.maxPath
     
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

入力

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

出力

5