Python程式：查詢二叉樹中最長連續路徑的長度

假設我們有一個二叉樹；我們必須找到二叉樹中最長的路徑。

所以，如果輸入是這樣的

那麼輸出將是5，因為最長的連續序列是[2, 3, 4, 5, 6]。

為了解決這個問題，我們將遵循以下步驟：

  • 如果根節點為空，則
    • 返回0
  • maxPath := 0
  • 定義一個函式helper()。這將接收節點
  • inc := 1, dec := 1
  • 如果節點的左子節點不為空，則
    • [left_inc, left_dec] := helper(節點的左子節點)
  • 否則，
    • [left_inc, left_dec] := [0, 0]
  • 如果節點的右子節點不為空，則
    • [right_inc, right_dec] := helper(節點的右子節點)
  • 否則，
    • [right_inc, right_dec] := [0, 0]
  • 如果節點的左子節點不為空，且節點值 - 左子節點值等於1，則
    • inc := max(inc, (left_inc + 1))
  • 否則，如果節點的左子節點不為空，且節點值 - 左子節點值等於-1，則
    • dec := max(dec, (left_dec + 1))
  • 如果節點的右子節點不為空，且節點值 - 右子節點值等於1，則
    • inc := max(inc, (right_inc + 1))
  • 否則，如果節點的右子節點不為空，且節點值 - 右子節點值等於-1，則
    • dec := max(dec, (right_dec + 1))
  • 如果節點的左子節點和右子節點都不為空，且左子節點值 - 節點值等於1，且節點值 - 右子節點值等於1，則
    • maxPath := max(maxPath, (left_dec + right_inc + 1))
  • 否則，如果節點的左子節點和右子節點都不為空，且左子節點值 - 節點值等於-1，則
    • maxPath := max(maxPath, (left_inc + right_dec + 1))
  • maxPath := max(maxPath, inc, dec)
  • 返回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

更新於：2020年12月2日

179 次瀏覽

開始你的職業生涯

透過完成課程獲得認證

開始學習
廣告