.leetcode(662. Maximum Width of Binary Tree)

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

 

1. 2022.03.01 시도

소요시간: 37분(4분 구상, 20분까지 코딩, 13분 재코딩, bfs), 11분(dfs)

// bfs
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        Queue<Long> lq = new LinkedList<>();
        lq.offer(1L);
        
        Long maxWidth = 0L;
        while(!queue.isEmpty()) {
            int size = queue.size();
            long start = Long.MAX_VALUE;
            long end = -1;
            for (int i=0; i<size; i++) {
                TreeNode current = queue.poll();
                long value = lq.poll();
                start = Math.min(start, value);
                end = Math.max(end, value);
                if (current != null) {
                    if (current.left != null) { 
                        queue.offer(current.left);
                        lq.offer((value-1)*2+1);
                    }

                    if (current.right != null) { 
                        queue.offer(current.right);
                        lq.offer((value-1)*2+2);
                    }
                }
            }

            long width = end - start + 1;
            maxWidth = Math.max(maxWidth, width);
        }
            
        return maxWidth.intValue();
    }
}

// dfs
class Solution {
    private List<Long> minList;
    private List<Long> maxList;
    public int widthOfBinaryTree(TreeNode root) {
        minList = new ArrayList<>();
        maxList = new ArrayList<>();
        
        dfs(root, 0, 0L);
        
        Long maxWidth = 0L;
        for (int i=0; i<minList.size(); i++) {
            long start = minList.get(i);
            long end = maxList.get(i);
            maxWidth = Math.max(maxWidth, end-start+1);
        }
        
        return maxWidth.intValue();
    }
    
    private void dfs(TreeNode root, int depth, long index) {
        if (root == null) {
            return;
        }
        
        if (minList.size() == depth) {
            minList.add(index);
        } else {
            minList.set(depth, Math.min(index, minList.get(depth)));
        }
        
        if (maxList.size() == depth) {
            maxList.add(index);
        } else {
            maxList.set(depth, Math.max(index, maxList.get(depth)));
        }
        
        dfs(root.left, depth+1, 2*index);
        dfs(root.right, depth+1, 2*index+1);
    }
}

풀이 접근 과정

처음에 보자마자 길이 구하닌깐 bfs로 접근해야겠다는 생각이 들었기에 queue를 써야겠다고 생각했다.
그리고 depth별로 끊어서 생각하기 위해 while문안에 for문을 두어 한층 한층 계산해야겠다고 생각했다.

null노드를 저장하면 길이 계산이 쉬울 거 같아서 처음에 포함했지만 타임아웃걸렸다.
그렇기에 약간 방법을 틀어 null노드를 제외하기 위해 길이값을 저장할 queue를 하나 더 세워야겠다고 생각했다.

최대 길이가 int max가 나올 수 있으므로 계산해주기 위해 int형으로 모두 정의했던 것을 long으로 변경했다.

 

느낀점

• 문제 봤을 때, null처리를 어떻게 할지가 키포인트라는 생각이 들었다. null을 넣을 것인지 말것인지는 늘 고민된다. 이번에는 안 넣는게 맞았다. 실제로 문제 풀때도 null넣는걸 먼저 풀어보고 더 효율적으로 풀어볼 때, null제외하는 방식으로 다시 풀어도 늦지 않을 것이다.
• dfs로 할때, left에서 부터 채워진다는 성질을 이용하면 첫번째 것만 저장해도 되고 이를 map으로 간단하게 써볼 수 있다.

class Solution {
    private Long maxWidth;
    private Map<Integer, Long> firstMap;
    public int widthOfBinaryTree(TreeNode root) {
        firstMap = new HashMap<>();
        maxWidth = 0L;
        
        dfs(root, 0, 0L);
        
        return maxWidth.intValue();
    }
    
    private void dfs(TreeNode root, int depth, long index) {
        if (root == null) {
            return;
        }
        
        if (!firstMap.containsKey(depth)) {
            firstMap.put(depth, index);
        }
        
        dfs(root.left, depth+1, 2*index);
        dfs(root.right, depth+1, 2*index+1);
        
        long start = firstMap.get(depth);
        maxWidth = Math.max(maxWidth, index- start + 1);
    }
}

- 다르게 풀어볼 수 없을까 해서 map을 두개 써서 dfs를 구현해보았다. 시간 복잡도로 보면 같고 공간만 더 늘어나는  것 같다. 양쪽을 구하면 더 빠르게 연산이 될거라 생각했는데 마지막 depth인지 아닌지를 판단할 수 없어서 노드 전체를 다 읽게된다.

class Solution {
    private Map<Integer, Long> leftMap;
    private Map<Integer, Long> rightMap;
    public int widthOfBinaryTree(TreeNode root) {
        leftMap = new HashMap<>();
        rightMap = new HashMap<>();
        
        leftDfs(root, 0, 0L);
        rightDfs(root, 0, 0L);
        
        Long maxWidth = 0L;
        for (int i=0; i<leftMap.size(); i++) {
            long start = leftMap.get(i);
            long end = rightMap.get(i);
            
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        
        return maxWidth.intValue();
    }
    
    private void leftDfs(TreeNode root, int depth, long index) {
        leftMap.computeIfAbsent(depth, x->index);
        
        if (root.left != null) {
            leftDfs(root.left, depth+1, 2*index);
        }
        if (root.right != null) {
            leftDfs(root.right, depth+1, 2*index+1);
        }
    }
    
    private void rightDfs(TreeNode root, int depth, long index) {
        rightMap.computeIfAbsent(depth, x->index);
        
        if (root.right != null) {
            rightDfs(root.right, depth+1, 2*index+1);
        }
        
        if (root.left != null) {
            rightDfs(root.left, depth+1, 2*index);
        }
    }
}

 

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형