Leetcode - 199. Binary Tree Right Side View

숲사람·2022년 9월 2일
0

멘타트 훈련

목록 보기
137/237

문제

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

해결

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;
    }
};
profile
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)

0개의 댓글