Leetcode - 199. Binary Tree Right Side View

문제

주어진 트리를 우측에서 바라볼때 노드 값을 리턴하라.

해결

BFS로 순회. root부터 queue에 넣고, pop하면서 처음으로 height가 커질때마다 값들을 ret Vector에 저장. 아주 흥미로운 문제 였다.

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ret;
        queue<pair<TreeNode *, int>> q;
        int cur_h = 0;
        
        if (root)
            q.push(make_pair(root, cur_h + 1));
        while (!q.empty()) {
            pair<TreeNode *, int> check = q.front();
            q.pop();
            TreeNode *node = check.first;
            if (check.second > cur_h) {
                ret.push_back(node->val);
                cur_h = check.second;
            }
            if (node->right)
                q.push(make_pair(node->right, cur_h + 1));
            if (node->left)
                q.push(make_pair(node->left, cur_h + 1));
        }
        return ret;
    }
};