Leetcode - 102. Binary Tree Level Order Traversal

문제

트리를 순회하는데 동일한 level에 있는 노드끼리 분류해서 값을 리턴하라. 아래 output참고.

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

해결 (DFS)

dfs 순회 하면서 2차원 벡터의 level 인덱스에 값을 push_back()한다. 문제는 level인덱스가 없을때인데, 그 조건은 ret.size()가 level과 같거나 작다면 아직 level인덱스에 값이 없다는 뜻이다. 그 조건일때만 첫 벡터를 생성해서 push_back() 한다.

class Solution {
    void level_order_travel(TreeNode *root, int level, vector<vector<int>> &ret) {
        if (root == NULL)
            return;
        if (ret.size() <= level) { /* there is no ret[level], need to addsign a new vector */
            vector<int> lv;
            lv.push_back(root->val);
            ret.push_back(lv);
        } else {
            ret[level].push_back(root->val);
        }
        level_order_travel(root->left, level + 1, ret);
        level_order_travel(root->right, level + 1, ret);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        level_order_travel(root, 0, ret);
        return ret;
    }
};

해결 (BFS)

BFS순회를 하면서, 현재 높이를 기록해뒀다가 증가하면 저장.

https://velog.io/@soopsaram/Leetcode-199.-Binary-Tree-Right-Side-View 풀이와 동일하게 BFS순회 함.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == NULL)
            return ret;
        vector<int> tmp;
        queue<pair<TreeNode *, int>> q;
        int prev_height = 0;
        
        if (root)
            q.push(make_pair(root, prev_height + 1));
        
        while (!q.empty()) {
            pair<TreeNode *, int> check = q.front();
            q.pop();
            TreeNode *node = check.first;
            int cur_h = check.second;
            
            if (cur_h == prev_height + 2) { // insert tmp to ret
                ret.push_back(tmp);
                prev_height++;
                tmp.clear();
            }
            if (cur_h == prev_height + 1) { // make tmp (current height's vector)
                tmp.push_back(node->val);
            }
            
            if (node->left) q.push(make_pair(node->left, cur_h + 1));
            if (node->right) q.push(make_pair(node->right, cur_h + 1));
        }
        ret.push_back(tmp); // insert the last tmp
        return ret;
    }
};