Binary Tree Right Side View: góc nhìn phụ thuộc vào cách bạn đi

Đứng bên phải cây nhị phân và nhìn sang trái. Bạn thấy một node mỗi level: node nào nằm xa nhất bên phải ở độ sâu đó. Bài toán yêu cầu trả về các giá trị đó, từ trên xuống dưới.

Chỉ vậy thôi. Câu hỏi không phải là đáp án là gì -- mà là cấu trúc duyệt nào cho bạn node ngoài cùng bên phải của mỗi level một cách tự nhiên nhất.

Với cây trên ([1,2,3,null,5,null,4]), góc nhìn từ phải là [1, 3, 4]. Level 0 cho node 1 (node duy nhất). Level 1 cho node 3 (ngoài cùng phải trong số 2 và 3). Level 2 cho node 4 (ngoài cùng phải trong số 5 và 4).

Đề bài

Cho root của một binary tree, trả về giá trị các node nhìn thấy khi đứng ở phía bên phải cây, theo thứ tự từ trên xuống dưới — mỗi level một node, node nằm xa nhất bên phải ở độ sâu đó. Đề gốc: LeetCode 199.

Ràng buộc:
- Số node trong cây nằm trong khoảng [0, 100].
- -100 <= Node.val <= 100

Constraints nói gì trước khi viết code

Số node trong [0, 100] và giá trị trong [-100, 100]. Không có con số nào ở đây tạo ra áp lực thực sự.

n <= 100 nghĩa là độ sâu recursion tối đa là 100 (chuỗi lệch hoàn toàn). Giới hạn recursion mặc định của Python là 1000. Stack overflow không phải mối lo -- chọn BFS lặp thay vì DFS đệ quy là lựa chọn thiết kế, không phải yêu cầu an toàn.

-100 <= val <= 100 bao gồm số âm và số 0. Thuật toán không bao giờ so sánh các giá trị với nhau; nó chỉ ghi lại chúng. Dải giá trị hoàn toàn không ảnh hưởng tới tính đúng đắn.

Điều constraint thực sự cho bạn biết: cả BFS lẫn DFS đều O(n) về time, và không cái nào vượt trội hơn cái kia về complexity class với n = 100. Lựa chọn giữa chúng phụ thuộc vào việc thuật toán nào diễn đạt cấu trúc bài toán tự nhiên hơn.

Approach 1: BFS -- snapshot từng level bằng queue

Dịch thẳng "node ngoài cùng phải mỗi level" thành code: xử lý node theo từng level và ghi lại node cuối cùng mỗi lần. BFS thực hiện điều này theo nghĩa đen.

Cơ chế then chốt: trước khi xử lý một level, snapshot len(queue) thành level_size. Con số đó cho bạn biết chính xác bao nhiêu node thuộc level này. Duyệt hết tất cả chúng, và node ở index level_size - 1 là node ngoài cùng phải -- thêm giá trị của nó vào result.

from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
 
        result = []
        queue = deque([root])
 
        while queue:
            level_size = len(queue)
 
            for i in range(level_size):
                node = queue.popleft()
 
                if i == level_size - 1:
                    result.append(node.val)
 
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
 
        return result

using System.Collections.Generic;
 
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        if (root == null) return new List<int>();
 
        var result = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            int levelSize = queue.Count;
 
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
 
                if (i == levelSize - 1) {
                    result.Add(node.val);
                }
 
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
 
        return result;
    }
}

Trace tay qua [1,2,3,null,5,null,4]

Ban đầu: queue = [1]

--- Level 0 (level_size = 1) ---
i=0: dequeue 1, i == level_size-1, result = [1]
     enqueue left=2, right=3
queue = [2, 3]

--- Level 1 (level_size = 2) ---
i=0: dequeue 2, i != level_size-1, bỏ qua
     enqueue left=null (bỏ qua), right=5
i=1: dequeue 3, i == level_size-1, result = [1, 3]
     enqueue left=null (bỏ qua), right=4
queue = [5, 4]

--- Level 2 (level_size = 2) ---
i=0: dequeue 5, i != level_size-1, bỏ qua
     không có con
i=1: dequeue 4, i == level_size-1, result = [1, 3, 4]
     không có con
queue = []

Trả về [1, 3, 4]

Time complexity: O(n). Mỗi node được enqueue và dequeue đúng một lần. Mỗi thao tác là O(1).

Space complexity: O(w) trong đó w là độ rộng tối đa của cây. Queue chứa tối đa một level đầy đủ tại một thời điểm. Trong trường hợp xấu nhất (cây nhị phân đầy đủ), level dưới cùng có n/2 node, làm cho space trở thành O(n).

Approach 2: DFS -- chiếm level ngay lần đầu ghé thăm

DFS đạt được kết quả tương tự qua một mental model hoàn toàn khác. Thay vì xử lý tất cả node ở một level cùng nhau, DFS ghi lại node đầu tiên gặp tại mỗi độ sâu mới. Mấu chốt: đi nhánh phải trước nhánh trái. Lần đầu tiên bạn chạm vào một độ sâu nhất định, bạn được đảm bảo đang ở node ngoài cùng phải sẽ được thăm ở độ sâu đó.

from typing import List, Optional
 
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
 
        def dfs(node, depth):
            if not node:
                return
 
            # Lần đầu thăm depth này -> node ngoài cùng phải cho đến giờ
            if depth == len(result):
                result.append(node.val)
 
            # Phải trước -- quan trọng cho tính đúng đắn
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
 
        dfs(root, 0)
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        DFS(root, 0, result);
        return result;
    }
 
    private void DFS(TreeNode node, int depth, List<int> result) {
        if (node == null) return;
 
        // Lần đầu thăm depth này -> node ngoài cùng phải cho đến giờ
        if (depth == result.Count) {
            result.Add(node.val);
        }
 
        // Phải trước -- quan trọng cho tính đúng đắn
        DFS(node.right, depth + 1, result);
        DFS(node.left, depth + 1, result);
    }
}

Điều kiện depth == len(result) là insight cốt lõi. Vì result được append đúng một lần mỗi level, len(result) bằng số level đã được chiếm. Khi depth == len(result), depth hiện tại đang được thăm lần đầu tiên.

Trace tay qua [1,2,3,null,5,null,4]

dfs(1, depth=0): depth(0) == len([]) -> result = [1]
  dfs(3, depth=1): depth(1) == len([1]) -> result = [1, 3]
    dfs(4, depth=2): depth(2) == len([1,3]) -> result = [1, 3, 4]
      dfs(null, depth=3): return
      dfs(null, depth=3): return
    dfs(null, depth=2): return
  dfs(2, depth=1): depth(1) != len([1,3,4]) = 3 -> bỏ qua
    dfs(5, depth=2): depth(2) != len([1,3,4]) = 3 -> bỏ qua
      dfs(null, depth=3): return
      dfs(null, depth=3): return
    dfs(null, depth=2): return

Trả về [1, 3, 4]

Node 2 và node 5 được thăm nhưng giá trị của chúng bị bỏ qua -- depth 1 và depth 2 đã được chiếm trước. Đây là phiên bản DFS của "chúng ta đã có node ngoài cùng phải cho level này rồi."

Time complexity: O(n). Mỗi node được thăm đúng một lần.

Space complexity: O(h) trong đó h là chiều cao cây. Call stack chứa tối đa h frame. Với cây cân bằng, h = log n; với chuỗi lệch, h = n. Điều này tốt hơn O(w) của BFS với cây cân bằng (vì log n < n/2), và tương đương hoặc kém hơn với cây lệch.

Một trường hợp lộ rõ sự khác biệt: subtree chỉ có nhánh trái

Xét [1,2,3,4] trong đó node 3 không có con nhưng node 2 có con trái (node 4):

BFS: Level 0 = [1], ngoài cùng phải = 1. Level 1 = [2, 3], ngoài cùng phải = 3. Level 2 = [4], ngoài cùng phải = 4. Kết quả: [1, 3, 4].

DFS (phải trước): thăm 1 (chiếm depth 0) -> 3 (chiếm depth 1) -> 2 (depth 1 đã chiếm, bỏ qua) -> 4 (chiếm depth 2). Kết quả: [1, 3, 4].

Cả hai đều đúng. Điều thú vị ở đây là node 4 là con trái, nhưng vẫn xuất hiện trong right-side view vì nó là node duy nhất ở độ sâu của mình. Không thuật toán nào quan tâm đến trái vs. phải một cách độc lập -- chỉ quan tâm đến việc là đại diện duy nhất hoặc ngoài cùng phải ở một depth nhất định.

Các edge case

Cây rỗng (root = null): BFS return ngay trước khi vào vòng lặp. dfs(null, 0) của DFS nhấn base case ngay lập tức. Cả hai trả về [].

Cây một node: BFS enqueue root, xử lý level 0 với level_size = 1, ghi lại nó. DFS thăm root ở depth 0, ghi lại nó, rồi recurse vào hai null. Cả hai trả về [root.val].

Cây lệch hoàn toàn về trái ([1,2,null,3,null,4]): Mỗi level chỉ có đúng một node -- node trái nhất. BFS xử lý từng level và thấy level_size = 1 mỗi lần, ghi lại mọi node. DFS đi phải (null mỗi level) trước, không tìm thấy gì, rồi đi trái -- nhưng depth vẫn chưa được chiếm, nên nó ghi lại con trái. Góc nhìn từ phải là toàn bộ chuỗi node. Cả hai xử lý đúng.

Cây lệch hoàn toàn về phải: Ngược lại với trên. BFS ghi lại node đơn ở mỗi level. DFS đi thẳng xuống chuỗi phải, chiếm từng depth liên tiếp. Kết quả giống hệt nhau.

Cây có giá trị âm (val = -50): thuật toán ghi lại giá trị, không bao giờ so sánh chúng với ngưỡng nào. Số âm không có gì đặc biệt.

Bảng so sánh

Với n = 100, sự khác biệt không đáng kể. Với cây lớn hơn (tưởng tượng bài toán tương tự ở n = 10^5), DFS tiết kiệm bộ nhớ thực sự với input cân bằng.

Approach nào tôi sẽ dùng

Tôi chọn DFS trong phỏng vấn. Điều kiện depth == len(result) không trực quan khi đọc lần đầu, nhưng khi bạn hiểu rồi, toàn bộ giải pháp chỉ là năm dòng Python không cần import. Không có queue để quản lý, không cần nhớ snapshot level_size, không có rủi ro off-by-one ở ranh giới vòng lặp.

BFS là đáp án sư phạm rõ ràng hơn vì "node ngoài cùng phải mỗi level" ánh xạ trực tiếp vào "node cuối cùng được dequeue trong mỗi batch BFS." Nếu bạn đang giải thích bài toán cho người mới gặp level-order traversal lần đầu, BFS là phương tiện dạy học tốt hơn. Nó không cần insight thông minh nào -- chỉ cần một vòng lặp theo level gọn gàng.

Nhưng nếu bạn đang viết code thực tế hoặc interviewer muốn phiên bản ngắn gọn nhất: DFS. Traversal phải-trước và guard depth == len(result) diễn đạt giải pháp theo cách khó đọc nhầm khi bạn đã hiểu pattern.

Pattern nền: level-indexed result construction

Approach DFS ở đây thuộc về một pattern tôi gọi là level-indexed result construction: thay vì nhóm các node ở một level lại với nhau (như BFS làm), bạn dùng kích thước của result list như một bộ đếm level đã được chiếm, và đảm bảo mỗi level chỉ được chiếm đúng một lần bằng cách kiểm soát thứ tự traversal.

Pattern này có thể tổng quát hóa. Bất kỳ bài toán nào cần "một thứ mỗi level" và có thể kiểm soát thứ tự traversal đều có thể dùng nó. Trade-off là BFS diễn đạt tư cách thành viên level một cách tự nhiên -- bạn có tất cả node ở một level trong queue cùng lúc -- trong khi DFS đòi hỏi bạn tin tưởng rằng một thứ tự traversal cụ thể đảm bảo node đúng được chiếm đầu tiên.

Vị trí trong series và bước tiếp theo

Đây là bài thứ 11 trong series trees. Các bài trước đã thiết lập các primitive duyệt cơ bản -- maximum depth (recursion trên chiều cao), invert binary tree (biến đổi cấu trúc), level order traversal (vòng lặp BFS), same tree (duyệt song song). Binary Tree Right Side View là bài đầu tiên trong series mà output có chủ ý là một phần: bạn nhìn thấy cây nhưng chỉ một lát cắt của nó. Thuật toán phải ghi lại có chọn lọc.

Binary Tree Level Order Traversal (102) là bài ngay trước. Ở đó, bạn ghi lại tất cả node mỗi level. Ở đây, bạn chỉ ghi lại node cuối. Nếu 102 đã quen thuộc, 199 thêm đúng một quyết định lọc lên trên.

Find Bottom Left Tree Value (513) là ngược lại: thay vì node cuối mỗi level, bạn muốn node đầu tiên ở level sâu nhất. DFS sẽ đi trái trước; BFS sẽ lấy node đầu tiên của batch sâu nhất.

Binary Tree Zigzag Level Order Traversal (103) mở rộng pattern level-order xa hơn: luân phiên thu thập trái-sang-phải và phải-sang-trái ở mỗi depth. Frame BFS từ bài này xử lý nó với một direction flag.

Populating Next Right Pointers in Each Node (116) chuyển đổi insight về level-grouping thành một dạng cấu trúc: liên kết các node cùng level thành linked list. Cùng cơ chế snapshot level của BFS -- level_size = len(queue) -- là công cụ thực hiện.