On this page

ข้อ 39 · LC199 Binary Tree Right Side View (มุมมองด้านขวา) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

คืน node ขวาสุดของแต่ละชั้น ด้วย BFS วนทีละชั้นแล้วเก็บตัวสุดท้าย

โจทย์ (LC199): กำหนด root ของ binary tree มาให้ ให้จินตนาการว่ายืนอยู่ทางด้านขวาของต้นไม้ ให้ return ค่าของ node ที่มองเห็นได้ เรียงจากบนลงล่าง (= node ขวาสุดของแต่ละ level — ถ้า level นั้นฝั่งขวาไม่มี node ก็จะเห็นตัวที่อยู่ขวาสุดเท่าที่มีแทน)

Example 1

Input:: root = [1,2,3,null,5,null,4]
Output:: [1,3,4]
Explanation:: เห็น 1 ที่ชั้น 1, เห็น 3 ที่ชั้น 2 (บัง 2 ไว้), เห็น 4 ที่ชั้น 3 (บัง 5 ไว้)

Example 2

Input:: root = [1,2,3,4]
Output:: [1,3,4]
Explanation:: ชั้น 3 มีแค่ node 4 (ลูกซ้ายของ 2) เพราะ node 3 ไม่มีลูกเลย จึงเห็น 4 เป็นตัวขวาสุดเท่าที่มีในชั้นนั้น

Example 3

Input:: root = [1,2,3,4,null,null,null,5]
Output:: [1,3,4,5]
Explanation:: ชั้น 3 มีแค่ node 4 ตัวเดียว (node 3 ไม่มีลูก) ชั้น 4 มีแค่ node 5 ซึ่งเป็นลูกซ้ายของ 4 แต่เป็นตัวเดียวในชั้นจึงมองเห็น

Constraints (ข้อจำกัด)

จำนวน node อยู่ระหว่าง 0 ถึง 100
-100 <= Node.val <= 100

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ BFS loop ทีละ level ตาม template แล้วเก็บเฉพาะ node ตัวสุดท้ายที่ pop ออกในแต่ละ level (ตำแหน่ง size - 1) ซึ่งคือ node ขวาสุดของ level นั้นพอดี

ถ้าคิดง่าย ๆ ว่า "คำตอบคือ right child ของทุก node" จะพลาด เพราะบาง level ฝั่งขวาว่างแต่ฝั่งซ้ายยังมี node การยึด "ตัวสุดท้ายใน level" จาก BFS แก้ปัญหานี้ได้หมด

ถ้า root เป็น None return [] ทันที
ตั้ง result = [] และ queue = deque([root])
loop while queue: จด size = len(queue)
loop for i in range(size): pop node ออกมา
ถ้า i == size - 1 (ตัวสุดท้ายของ level) append node.val เข้า result
append left child ก่อน right child เข้า queue เสมอ เพื่อให้ขวาสุดออกท้ายสุด

จุดพลาดที่พบบ่อย

เผลอเก็บแต่ node.right จะพลาดกรณี level นั้นฝั่งขวาว่างแต่ฝั่งซ้ายมี node — ต้องยึด "ตัวสุดท้ายใน level" และอย่าลืมเช็ค root เป็น None ตั้งแต่ต้น

ไล่ทีละสเต็ป

จำลองบนต้น [1,2,3,null,5,null,4] — คอลัมน์ "เก็บ" คือตัวที่ i == size-1

level	node ใน level (ซ้าย→ขวา)	size	ตัวสุดท้าย (เก็บ)
1	[1]	1	1
2	[2, 3]	2	3
3	[5, 4]	2	4

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

# LeetCode ให้ class นี้มาให้แล้ว ที่เขียนไว้ตรงนี้เพื่อให้บล็อกนี้รันได้เองทั้งก้อน
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque

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

def rightSideView(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:            # ตัวสุดท้ายของชั้น = ขวาสุด
                result.append(node.val)
            if node.left:
                queue.append(node.left)  # ต้องใส่ซ้ายก่อนขวา
            if node.right:
                queue.append(node.right) # เพื่อให้ขวาสุดออกท้ายสุด
    return result

# ต้นไม้ [1, 2, 3, null, 5, null, 4]
root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))
print(rightSideView(root))

Output

[1, 3, 4]

หัวใจคือใช้ template วนทีละชั้น แล้วเช็คว่า i == size - 1 ไหม ถ้าใช่แปลว่าเป็นตัวสุดท้ายที่ออกจากชั้นนี้ = ขวาสุด เก็บค่าเข้า result ที่ต้อง append ลูกซ้ายก่อนลูกขวาเสมอ เพื่อรับประกันว่าภายในชั้นถัดไป node จะเรียงซ้ายไปขวา ตัวที่ออกท้ายสุดจึงเป็นตัวขวาสุดจริง ๆ

จุดพลาดที่พบบ่อยคือเผลอคิดว่าคำตอบคือลูกขวาของทุก node หรือเก็บแต่ node.right ซึ่งจะพลาดกรณีที่ชั้นนั้นฝั่งขวาว่างแต่ฝั่งซ้ายมี node การยึดตำแหน่ง "ตัวสุดท้ายในชั้น" แก้ปัญหานี้ได้หมด อย่าลืมเช็ค root เป็น None ตั้งแต่ต้นด้วย

Time O(n) แตะทุก node ครั้งเดียว · Space O(w) โดย w คือความกว้างมากสุดของต้นไม้ = จำนวน node มากสุดในคิวพร้อมกันในหนึ่งชั้น กรณีแย่สุด w ราว ๆ n/2

💡 สรุป pattern

BFS วนทีละชั้นด้วย size = len(queue) แล้วเลือก node ตามตำแหน่งในชั้น (ตัวแรก/ตัวสุดท้าย/ทุกตัว) ตอบโจทย์ "ต่อชั้น" ได้แทบทุกแบบ