題目網址：https://leetcode.cn/problems/binary-tree-right-side-view/

題意：給一 BT 的 root, 想像你站在 BT 的右側, 按照從頂部到底部的順序, 返回你從右側所能看到的 node.val。

Solution 1：

想法：利用 BFS

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) {
            return {};
        }

        vector<int> res;
        queue<TreeNode*> q;
        q.emplace(root);

        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto cur = q.front();
                q.pop();

                // 把每層最後一個 node 給 push 到 res 中
                if (i == 1) {
                    res.emplace_back(cur->val);
                }

                if (cur->left) {
                    q.emplace(cur->left);
                }

                if (cur->right) {
                    q.emplace(cur->right);
                }
            }
        }
        return res;
    }
};
  • time：$O(n)$ ➔ 每個 node 皆被遍歷一次
  • space：$O(n)$ ➔ 撇除要返回的 array, 在 while loop 迭代的過程中, q 的元素個數不超過 n

Solution 2：

想法：利用 DFS, 遍歷順序為 root -> right -> left, 並用 depth 紀錄當前 root 的深度, 而 maxDepth 紀錄當前拜訪到的最大深度。

  • 若遞迴拜訪的 root 滿足 depth > maxDepth, 代表這是下一層最靠右的 node, 則把該 node 加入到 res 中, 並更新 maxDepth

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        int maxDepth = -1;
        dfs(root, 0, maxDepth, res);
        return res;
    }

private:
    void dfs(TreeNode* root, int depth, int& maxDepth, vector<int>& res){
        if (!root) {
            return;
        }

        if (depth > maxDepth) {
            res.emplace_back(root->val);
            maxDepth = depth;
        }

        // 先拜訪 right, 再拜訪 left
        dfs(root->right, depth + 1, maxDepth, res);
        dfs(root->left, depth + 1, maxDepth, res);
    }
};
  • time：$O(n)$ ➔ 每個 node 皆被遍歷一次
  • space：$O(n)$ ➔ 遞迴深度不超過 n