LeetCode 199. Binary Tree Right Side View [Medium] [C++] 解題筆記

 Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

 

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

想法:

    這題還蠻簡單的可以直接做 level order traverse 然後照提議把每層的最右邊的node存起來就好。

另外也可以用 dfs traverse，我們可以照 URL 的順序遍歷，每個 level只有最右邊的 node 會被放入 res中，

所以當 res.size() < level 的時候表示當前的 node 是該 level的最右邊的 node。

完整程式碼:

解法一:(BFS)
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) { return res; }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int q_size = q.size();
            res.push_back(q.front()->val);
            for (int i = 0; i < q_size; i++) {
                auto cur = q.front();
                q.pop();
                if (cur->right) { q.push(cur->right); }
                if (cur->left) { q.push(cur->left); }
            }
        }
        return res;   
    }
};

解法二:(DFS)

/* DFS solution */
class Solution {
public:
    void dfs(TreeNode* root, int level, vector<int>& res) {
        if (root == nullptr) { return; }
	// only first node in each level will be inserted
        if (res.size() < level) { res.push_back(root->val); }
        dfs(root->right, level + 1, res);
        dfs(root->left, level + 1, res);
        return;
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root, 1, res);
        return res;
    }
};