โปรแกรมหาโหนดที่ลึกเป็นอันดับสองในต้นไม้แบบทวิภาคใน Python

มีต้นไม้แบบทวิภาค หาความลึกของใบที่ลึกเป็นอันดับสอง (ถ้ามีใบลึกสุดหลายใบ ใบอันดับสองคือระดับถัดไป) รากลึก 0

เช่น ต้นไม้ที่มีโหนด 7,8 ลึกสุด ให้ 1 (โหนด 3)

ขั้นตอนการแก้ปัญหา

• BFS ระดับต่อระดับ เก็บ nodes ของระดับปัจจุบัน
• ติดตาม prev (ลึกอันดับสอง) และ now (ลึกสุด)
• เมื่อเจอใบแรกในระดับ ให้อัปเดต prev=now, now=count
• คืนค่า prev

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

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

class Solution:
    def solve(self, root):
        if root is None: return None
        nodes = [root]
        count = prev = now = 0
        while nodes:
            new = []; flag = True
            for node in nodes:
                if flag and not node.left and not node.right:
                    prev = now; now = count; flag = False
                if node.left: new.append(node.left)
                if node.right: new.append(node.right)
            nodes = new; count += 1
        return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

อินพุต

root = TreeNode(2) ...

เอาต์พุต

1