.leetcode(515. Find Largest Value in Each Tree Row)

https://leetcode.com/problems/find-largest-value-in-each-tree-row/

 

1. 2022.01.30 시도

소요시간: 30분 이상(다른 일때문에 측정x)

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> depthQueue = new LinkedList<>();
        queue.offer(root);
        depthQueue.offer(0);
        while(!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            Integer depth = depthQueue.poll();
            
            if (temp.left != null) {
                queue.offer(temp.left);
                depthQueue.offer(depth+1);
            }
            
            if (temp.right != null) {
                queue.offer(temp.right);
                depthQueue.offer(depth+1);
            }
            
            if (output.size() <= depth) {
                output.push(temp.val);
            } else {
                int max = output.pop();
                output.push(Math.max(max, temp.val));
            }
            
        }
        
        Collections.reverse(output);
        return output;
    }
}

풀이 접근 과정

보자마자 bfs로 접근하면 되겠다는 생각이 들었다.

고려해야할 것은 height을 어떻게 측정할지 여부였다. 처음에는 node를 카운트해서 적절히 2로 나누어 가지려고 했는데 그건 실패했다. 공간을 2배로 쓰더라도 queue를 하나 더 두고 같이 add,poll하는게 더 좋아보였다.

또한 하나의 문제는 output의 max를 갱신을 어떻게 잘하느냐였다. LinkeList를 써서 stack으로 push, pop하면서 비교했다.

 

느낀점

• 3가지 포인트가 있었다. 어떻게 depth를 나타낼 것인지, 또하나는 어떻게 max를 갱신할 것인지였다. 전자는 queue를 하나 더 둠으로써 해결했고 후자는 stack을 이용하여 해결하였다. 마지막 하나는 depth를 어떻게 판단하냐인데 나같은 경우는 size로 비교했다. 
• 그리고 queue의 메소드는 offer와 poll이였다..
• 재밌는 포인트는 queue르 이전 노드 갯수만큼 짤라서 depth를 확인하는 방법도 있었다.

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        if (root == null) {
            return output;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int max = Integer.MIN_VALUE;
            int n = queue.size();
            for (int i=0; i<n; i++) {
                TreeNode treeNode = queue.poll();    

                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }

                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
                max = Math.max(max, treeNode.val);
            }
            
            output.add(max);
        }
        
        return output;
    }
}

• dfs로도 풀 수 있다. dfs에서는 add, set을 써서 해결했다. set method를 몰랐네..

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        recursive(root, output, 1);
        return output;
    }
    
    public void recursive(TreeNode root, List<Integer> output, int depth) {
        if (root == null) {
            return;
        }
        
        if (output.size() < depth) {
            output.add(root.val);
        } else {
            int max = output.get(depth-1);
            output.set(depth-1, Math.max(max, root.val));
        }
        
        recursive(root.left, output, depth+1);
        recursive(root.right, output, depth+1);
    }
}

 

---

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

반응형