leetcode662. 두 갈래 나무 최대 너비

제목 링크:https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
제목: 이 나무의 최대 폭을 얻기 위해 두 갈래 트리를 지정합니다.트리의 너비는 모든 레이어의 최대 너비입니다.이 두 갈래 나무는 만 두 갈래 나무(full binary tree)와 구조가 같지만 일부 노드는 비어 있다.
각 층의 너비는 두 개의 단점 (이 층의 가장 왼쪽과 가장 오른쪽의 비공식 노드, 두 개의 단점 사이의null 노드도 길이를 계산함) 사이의 길이로 정의됩니다.
예 1:
입력:

           1
         /   \
        3     2
       / \     \  
      5   3     9 

출력: 4 설명: 최대 값은 나무의 3층에 나타나고 너비는 4(5,3,null,9)이다.예 2:
입력:

          1
         /  
        3    
       / \       
      5   3     

출력: 2 설명: 트리의 3층에 최대 값이 나타나고 너비는 2(5,3)입니다.예 3:
입력:

          1
         / \
        3   2 
       /        
      5      

출력: 2 설명: 최대 값은 트리의 2층에 나타나고 너비는 2(3,2)입니다.예 4:
입력:

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7

출력: 8 해석: 최대 값은 나무의 4층에 나타나고 너비는 8(6,null,null,null,null,null,null,7)이다.주의: 답안은 32비트의 기호 정수가 있는 표시 범위 내에 있다.
사고방식: bfs와 dfs 두 가지 방식을 사용할 수 있는데 핵심 사상은 각 층의 가장 왼쪽에 있는 노드를 기록하는 것이다.bfs에 대해 맵을 이용하여 각 노드가 두 갈래 나무에 있는 위치를 표시하고 뿌리 노드는 1부터 시작합니다.각 층의 노드에 대해 이 층의 가장 왼쪽 노드의 위치를 각각 빼면 현재 층의 너비이다.code 1:

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(root==NULL) return 0;
        queue<TreeNode*> Q;
        unordered_map<TreeNode*,int> mp;
        return bfs(Q,root,mp);
    }
    int bfs(queue<TreeNode*> &Q,TreeNode* root,unordered_map<TreeNode*,int> &mp){
        int cnt=0;
        Q.push(root);
        mp[root]=1;
        while(!Q.empty()){
            TreeNode *begin=Q.front();
            int left=mp[begin];
            int size=Q.size();
            for(int i=0;i<size;i++){
                TreeNode *front=Q.front();
                Q.pop();
                int ind=mp[front];
                cnt=max(ind-left+1,cnt);
                
                if(front->left){
                    Q.push(front->left);
                    mp[front->left]=ind*2;
                }
                if(front->right){
                    Q.push(front->right);
                    mp[front->right]=ind*2+1;
                }
            }
        }
        return cnt;
    }
};

dfs에 대해 같은 이치로 맵을 이용하여 각 층의 가장 왼쪽 위치를 표시하고 한 층이 갱신될 때마다 이 층의 넓이를 계산한다.code 2:

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(root==NULL) return 0;
        unordered_map<int,int> mp;
        int cnt=0;
        dfs(root,0,1,mp,cnt);
        return cnt;
    }
    void dfs(TreeNode *root,int level,int ind, unordered_map<int,int> &mp,int &cnt){
        if(root==NULL) return;
        if(mp.find(level)==mp.end())//     
            mp[level]=ind;
        cnt=max(cnt,ind-mp[level]+1);
        
        dfs(root->left,level+1,ind*2,mp,cnt);
        dfs(root->right,level+1,ind*2+1,mp,cnt);
        
    }
};

사고방식은 다음과 같다.https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106654/JavaC%2B%2B-Very-simple-dfs-solution