LeetCode #543 Diameter of Binary Tree: เส้นทางยาวสุดผ่านโหนดใดก็ได้
น้องกายEngineering
Diameter คือจำนวนเส้นเชื่อมในเส้นทางยาวสุดระหว่างโหนดใดๆ สองโหนด เส้นทางไม่จำเป็นต้องผ่านราก
วิธีที่ 1: ทุกโหนดคำนวณความสูงซ้าย+ขวา
ที่แต่ละโหนด candidate = สูงซ้าย + สูงขวา เก็บค่ามากสุดขณะ DFS คืนความสูงของโหนดให้พาเรนต์ เวลา O(n)
วิธีที่ 2: คำนวณความสูงแยกทุกรากย่อยแบบนาอีฟ
เรียกฟังก์ชันสูงซ้ำซ้อน O(n²) ใช้เป็น oracle บนต้นเล็ก
วิธีที่ 3: แปลงเป็นกราฟแล้ว BFS สองครั้ง
หาเส้นผ่านศูนย์กลางแบบต้นไม้ทั่วไป หนักเกินโจทย์นี้
วิธีที่ 4: DP บนต้นไม้เก็บคู่ (สูง, diameter)
คล้ายวิธี 1 แต่คืนทูเพิลชัดเจน อ่านง่ายในบางภาษา
from __future__ import annotations
import unittest
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def diameter_of_binary_tree(root: TreeNode | None) -> int:
best = 0
def height(node: TreeNode | None) -> int:
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best
class DiameterTests(unittest.TestCase):
def test_example(self):
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
self.assertEqual(diameter_of_binary_tree(root), 3)
def test_single(self):
self.assertEqual(diameter_of_binary_tree(TreeNode(1)), 0)
if __name__ == "__main__":
unittest.main()เลือกวิธีไหนดี
- สัมภาษณ์ / โปรดักชันแนวต้นไม้: วิธี 1 หรือ 4
- ตรวจคำตอบ: วิธี 2 บนอินพุตเล็ก
- อย่าใช้วิธีกราฟยกใหญ่ถ้าไม่จำเป็น
Recap
- diameter นับเส้น ไม่นับโหนด
- อัปเดต best ที่ทุกโหนดจากสูงซ้าย+ขวา
- เทสต์ต้นโหนดเดียวต้องได้ 0