[Day6/15] LeetCode 75

Level 1 : day 6

오늘은 LeetCode 75 Level 1 을 시작한지 6일차다. (사실 풀어놓고 한번에 올리는 중)

오늘의 주제는 트리(Tree) 이다.

This study plan is for those who want to prepare for technical interviews but are uncertain which problems they should focus on. The problems have been carefully curated so that levels 1 and 2 will guide beginner and intermediate users through problems that cover the data structures and algorithms necessary to succeed in interviews with most mid-tier companies. While level 3 provides material to help users whose targets are top-tier companies.

589. N-ary Tree Preorder Traversal (문제링크)

트리의 root 가 주어지면 preorder 순회를 구현해야한다.

풀이과정

제한사항에서 확인 할 수 있다싶이 $O(n^2)$ 로 푼다면 TLE 가 뜬다.
따라서, 한 번의 iterative 을 통하여 최저가를 갱신해 나가면서 maxProfit 을 계산해주면 된다.

이렇게 할 경우 시간복잡도는 $O(n)$ 이 된다.

Java Solution

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        
        if (n == 1) return 0;
        
        int min = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, prices[i]);
            
            maxProfit = Math.max(maxProfit, prices[i] - min);
        }
        
        return maxProfit;
    }
}

102. Binary Tree Level Order Traversal (문제링크)

주어진 이진 트리의 노드들을 각 레벨끼리 나누는 문제다.

풀이과정

이 문제는 주어진 트리의 depth 을 알면 쉽게 해결 할 수 있다.

1. depth 을 구한다.

2. depth 만큼 list<list> 을 빈 list 로 선언한다.

3. 재귀 함수를 통하여 각 level (인덱스)에 위치한 리스트에 value 을 add 해준다.

Java Solution

class Solution {
    private List<List<Integer>> list;
    
    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        
        if (left > right) return left + 1;
        else return right + 1;
    }
    
    private void traversal(TreeNode root, int level) {
        if (root == null) return;
        
        List<Integer> temp = list.get(level);
        temp.add(root.val);
        
        traversal(root.left, level+1);
        traversal(root.right, level+1);
        
    }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        list = new ArrayList<>();
        
        int maxDepth = getDepth(root);

        if (maxDepth == 0) return list;
        
        for (int i = 0; i < maxDepth; i++) {
            list.add(new ArrayList<>());
        }
        
        traversal(root, 0);
        
        return list;
        
    }
}

Tree 자료구조는 대체적으로 그림을 그리면 쉽게 해결이 가능하다!
아직까지는 쉬워서 다행이다..!