[leetCode] 102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/?envType=problem-list-v2&envId=breadth-first-search

Binary Tree Level Order Traversal - LeetCode

 

이진 트리가 주어지고, 해당 트리의 노드 값들을 레벨 순서대로 순회하여 반환하는 문제이다.

저번 leetCode 101번 문제를 풀면서 사용했던 queue를 이용한 하나하나 체크하는 로직 그대로 가져와 응용하면 될 것 같았다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <queue>

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

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            int levelSize = q.size();
            vector<int> currentDepthValue;

            for(int i=0; i<levelSize; i++)
            {
                TreeNode* node = q.front(); 
                q.pop();
                                
                currentDepthValue.push_back(node->val);

                if(node->left != nullptr)
                    q.push(node->left);
                
                if(node->right != nullptr)
                    q.push(node->right);
            }

            result.push_back(currentDepthValue);
        }

        return result;
    }
};

이 문제는 

root의 leftNode를 검사하고, rightNode를 검사하여, 층 별로 쭉 검사해서 vector에 담는 구조이다.

 

먼저 트리의 같은 층의 노드의 개수가 여러 개 일 수 있다는 점을 감안하여 for문을 돌아야 겠다는 생각을 먼저했다.

그리고, 해당 같은 층 노드들을 모아줄 수 있는 하나의 vector가 존재해야겠다고 생각하였고,

여기서 반환값이 vector<vector<int>>이니까, 여기서 return result벡터를 하나 만들어 반환하게 해야 겠단 생각을 했다.

 

하지만 여기서 의문점은 "이걸 DFS 방식으로 풀 수 없을까?" 라는 생각이 들었다.

아래는 해당 DFS로 푼 방식이다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <queue>

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> result;
        
        Search(root, 0, result);
        
        return result;
    }
    
    void Search(TreeNode* node, int depth, vector<vector<int>>& vec)
    {
        if(node == nullptr)
            return;
        
        if(vec.size() == depth)
            vec.push_back(vector<int>());
        
        vec[depth].push_back(node->val);

        Search(node->left, depth+1, vec);
        Search(node->right, depth+1, vec);
    
    }
};

먼저 깊이별로 vector를 생성해야 하니까,  vector<int>를 해당 깊이 층별로 요소들을 모아놓는 바구니라 생각하고 접근한다.

그리고 해당 층별로 요소들의 값들을 벡터에 담아서 푼 것이다.