binary tree 탐색 (BFS)

노드 레벨 순회(Level-order Traversal)

너비 우선 탐색(BFS)은 트리나 그래프 구조에서 traverse 및 search 할 수 있는 알고리즘이다.
이를 이용해서 레벨 순회를 구현할 수 있다.

(출처 leetcode)

아래 코드는 큐를 이용해 구현한 코드이다.

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;

        
        queue<TreeNode*> que;
        que.push(root);
        
        while(!que.empty()){
            
            vector<int> temp;
            TreeNode* pre_node;
            int level_search_size = que.size();
            
            for(int i=0;i<level_search_size;++i){
                pre_node = que.front();
                temp.push_back(pre_node->val);
                que.pop();
                if(pre_node->left) que.push(pre_node->left);
                if(pre_node->right) que.push(pre_node->right);
            }
            res.push_back(temp);
        }
        
        
        return res;
    }

큐와 반복문 for를 통해 각 레벨에 포함되는 노드에 접근하였다.

너비 탐색은 주로 자료구조인 queue를 사용하여 구현할 수 있다.