[Java] leetcode 662. Maximum Width of Binary Tree

문제

https://leetcode.com/problems/maximum-width-of-binary-tree/description/

Maximum Width of Binary Tree - LeetCode

 

알아야 할 개념

• BFS 탐색

풀이

배열로 세그먼트 트리 만드는 과정을 연상하여 풀이했다.

root. left -> 현재 idx * 2 + 1

root right -> 현재 idx * 2 + 2

 풀이는 다음과 같다.

1. 큐를 이용해 BFS를 구현한다.
2. 탐색의 각 레벨에서 다음을 반복한다.
   1.  width 시작점인 left와 right 지점을 잡는다.
   2. Current Node Left 가 존재하면 , idx * 2 +1 을 왼쪽 자식 노드의 인덱스로 잡아 , left, right를 업데이트한다.
   3. Current Node Right 가 존재하면 , idx * 2 +2 을 오른쪽 자식 노드의 인덱스로 잡아 , left, right를 업데이트한다.
   4. left , right 둘다 -1 아닌경우만 width값을 계산한다.
3. 정답을 리턴한다.

 

코드

자바

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 class Pair{
     TreeNode n;
     int idx;
     Pair(TreeNode n, int idx){
         this.n = n;
         this.idx = idx;
     }
     public TreeNode getTn(){
         return this.n;
     }
     public int getIdx(){
         return this.idx;
     }
 }
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair> Q = new LinkedList<>();
        int L = 0;
        int ret = 1;//return value
        int idx = 0;
        int val = 0;
        if(root == null)return 0;
        Q.offer(new Pair(root, 0));
        while(!Q.isEmpty()){
            int size = Q.size();
            int left = -1;
            int right = -1;
            idx = 0;
            for(int i =0 ;i < size;i ++){
                Pair p = Q.poll();
                if(p.getTn().left != null){
                    val = p.getIdx() * 2 + 1;
                    if(left == -1)
                        left = val;
                    else{
                        right = val;
                    }
                    Q.offer(new Pair(p.getTn().left, val));
                }
                if(p.getTn().right != null){
                    val = p.getIdx() * 2 +2;
                    if(left == -1)
                        left = val;
                    else{
                        right = val;
                    }
                    Q.offer(new Pair(p.getTn().right, val));
                }
            }
            if(left != -1 && right != -1)
                ret = Math.max(ret, right - left + 1);
            L++;
        }
        return ret;
    }
}