Python程式：查詢給定樹中最大的二叉搜尋子樹

假設我們有一個二叉樹，我們需要找到作為二叉搜尋樹的最大的子樹（節點數最多）。

所以，如果輸入是這樣的：

那麼輸出將是

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

• max_size := [0]
• max_node := [null]
• 定義一個函式traverse()。它將接收節點作為引數
• 如果節點為空，則
  • 返回null
• left := traverse(節點的左子節點)
• right := traverse(節點的右子節點)
• lst := left + [節點的值] + right
• 如果lst已排序，則
  • 如果max_size[0] < lst的大小，則
    • max_size[0] := lst的大小
    • max_node[0] := 節點
• 返回lst
• traverse(根節點)
• 從主方法返回max_node[0]

示例 (Python)

讓我們看看下面的實現以更好地理解：

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):
      max_size = [0]
      max_node = [None]
      def traverse(node):
         if not node:
            return []
      left = traverse(node.left)
      right = traverse(node.right)
      lst = left + [node.val] + right
      if sorted(lst) == lst:
         if max_size[0] < len(lst):
            max_size[0] = len(lst)
            max_node[0] = node
      return lst

   traverse(root)
   return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

輸入

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

輸出

4, 5, 6,

Arnab Chakraborty

更新於：2020年12月12日

瀏覽量：115

啟動您的職業生涯

完成課程獲得認證

開始學習