[c++][LeetCode Curated Algo 170][314. Binary Tree Vertical Order Traversal]

문제 

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

 

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

 

 

 

 

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

 

 

 

 

 

 

 

 

한줄해석 

위와 같은 tree 구조가 들어오면 왼쪽부터 세로로 읽어서 출력해라 

 

 

풀이포인트

1. tree구조에 접근 및 사용 할 수 있어야 한다. 

2. 넓이 탐색(BFS) 을 사용 할 수 있는가. 

3. tree 구조의 depth를 저장하려면 어떤식으로 방문해야하는가. 

 

추가상식 

tree구조를 넓이탐색으로 방문하기, 혹은 깊이탐색으로 방문하는 코드 외워두기 

// BFS로 방문 할 경우 

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> tmp;
        queue<TreeNode*> q;
        q.push(root); // 이렇게 하면 제일 앞쪽 treenode가 q에 들어간다. 
        
        while(!q.empty()){          
           TreeNode* t = q.front();
           q.pop();
           cout << t->val << endl;
           if(t->left)
               q.push(t->left);       // 좌우 추가해주기 
           if(t->right)
               q.push(t->right);
        }
        
        return tmp;
    }
};


// DFS로 방문 할 경우

    map<int, vector<int>> x;
    void traversal(TreeNode* node, int idx){
        if (!x.count(idx)){
            vector<int> tmp(0);
            x[idx] = tmp;
        }
        x[idx].push_back(node->val);
        if (node->left) traversal(node->left, idx - 1);
        if (node->right) traversal(node->right, idx + 1);
    }

 

 

   코드 

 

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> output;
        
        if(!root){
            return output;
        }
        
        
        queue<pair<int,TreeNode*>> q;
        map<int, vector<int>> m;
        q.push(make_pair(0,root));
        
        while(!q.empty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode* t = q.front().second;
                int num = q.front().first;
                q.pop();
                m[num].push_back(t->val);
                if(t->left)
                    q.push(make_pair(num-1, t->left));
                if(t->right)
                    q.push(make_pair(num+1, t->right));
            }
        }
        
        for(auto& v : m){
            output.push_back(v.second);
        }
        return output;
  
    }
};