โปรแกรมหาย่อยต้นไม้ค้นหาไบนารีที่ใหญ่ที่สุดใน Python

สมมติว่าเรามีต้นไม้ไบนารี (binary tree) เราต้องการหาย่อยต้นไม้ (subtree) ที่ใหญ่ที่สุด (มีโหนดมากที่สุด) ซึ่งเป็น Binary Search Tree (BST)

เช่น ถ้าต้นไม้รากคือ 12 ซ้าย 3 ขวา 5 (ซ้าย 4 ขวา 6) ผลลัพธ์จะเป็นย่อยต้นไม้ที่รากคือ 5 ประกอบด้วย 4, 5, 6

ขั้นตอนการแก้ปัญหา (Inorder Traversal + Check Sorted)

• max_size := [0], max_node := [None]
• ฟังก์ชัน traverse(node):
  • ถ้า node is None คืน []
  • left := traverse(node.left), right := traverse(node.right)
  • lst := left + [node.val] + right (inorder traversal)
  • ถ้า lst เรียงลำดับแล้ว (sorted):
    • ถ้า max_size[0] < len(lst) อัปเดต max_size และ max_node
  • คืน lst
• เรียก traverse(root) แล้วคืน max_node[0]

ตัวอย่างโค้ด

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,