โปรแกรมตรวจสอบว่า BST อยู่ใน Binary Tree หรือไม่ใน Python

กำหนด Binary Tree ต้องการหาซับทรีที่ใหญ่ที่สุดซึ่งเป็น Binary Search Tree (BST) และคืนค่ารูทโหนดของ BST นั้น

ตัวอย่าง

ผลลัพธ์ BST ที่ใหญ่ที่สุด:

Inorder traversal: 3, 4, 5

วิธีแก้ปัญหา

1. ใช้ DFS (Post-order traversal) ตรวจสอบแต่ละซับทรี
2. ติดตามขนาด BST ที่ใหญ่ที่สุด (c) และรูทของมัน (m)
3. คืนค่าโหนดรูท m ของ BST ที่ใหญ่ที่สุด

เงื่อนไข BST

• โหนดซ้าย ≤ โหนดปัจจุบัน ≤ โหนดขวา
• ซับทรีซ้ายและขวาต้องเป็น BST ด้วย

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

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.val, end=', ')
        print_tree(root.right)

def solve(root):
    c, m = 0, None
    
    def recurse(node):
        nonlocal c, m
        if node:
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            
            if (node.left is None or node.left.val <= node.val) and \
               (node.right is None or node.val <= node.right.val):
                count = left_val + right_val + 1
            
            if count > c:
                c = count
                m = node
            return count
        return 0
    
    recurse(root)
    return m

tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))

อินพุต / เอาต์พุต

Input:  tree = make_tree([1, 4, 6, 3, 5])
Output: 3, 4, 5,

หมายเหตุ: ฟังก์ชัน print_tree ทำ inorder traversal เพื่อแสดงค่า BST จากน้อยไปมาก