.leetcode(543. Diameter of Binary Tree)

문제

https://leetcode.com/problems/diameter-of-binary-tree/

문제 풀기 전

1. 트리는 기본 문제로 앞에 2개정도 풀어서 왠지 금방 풀 수 있을거 같았다. 그러나 그렇지 않았다.
2. 각 노드별로 가장큰 것의 합을 구하고 한번 더 순회에서 가장 큰값만 가져오려고 하였다.
3. O(n)정도의 시간이 걸리지 않을까 한다.

직접 푼 풀이

소요시간: 39분(08:43 ~ 09:22)

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        maxDepth(root);

        return searchMax(root);

    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        root.val = left + right;
        return Math.max(left, right) + 1;
    }

    public int searchMax(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = searchMax(root.left);
        int right = searchMax(root.right);

        return Math.max(root.val, Math.max(left, right));
    }
}

느낀점

1. 이렇게 푸는게 맞나라는 생각이 많이 든다. 그래도 논리적으로 충분히 가능할거라 생각했다. 그리고 사실 다른 방법이 생각이 나지 않았다.
2. 솔루션은 전역변수 치트키를 썼다. 전역변수로 max를 갖고 있었기에 금방 풀이가 가능하다. 솔루션은 노드의 개수를 세고 있음에 주의해야한다. 그래서 처음에 1을 세팅한것도 root가 아예없어도 길이는 0이 나올 수 있고, root가 노드 1개만 있을때도 역시 길이는 0이 나올 수 있다. 우리의 목적은 길이를 구하는 것이기에 maxNodeCount - 1을 해야 결과값이 제대로 나온다.
3. 이렇게 리커션으로 하는건 공간을 쓰는걸로 의미해서 공간복잡도도 O(n)으로 풀이된다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    int maxNodeCount;
    public int diameterOfBinaryTree(TreeNode root) {    
        maxNodeCount = 1;

        depth(root);

        return maxNodeCount -1;
    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = depth(root.left);
        int right = depth(root.right);
        maxNodeCount = Math.max(maxNodeCount, left + right + 1);
        return Math.max(left, right) + 1;
    }

누적되는 알고리즘 접근 설명서

1. 제한값이 있는지 확인한다.

2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.

3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.

4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.

5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.

6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.

7. TreeNode는 left,right,val으로 구성해볼 수 있고 ListNode는 val,next로 구성해볼 수 있다.

8. ListNode문제가 나오면 꼭 그림으로 next관계를 이해해보자. 그리고 기존의 데이터를 이용해서 이어잘라붙이기에 대한 시도도 꼭 해보자.

9. 배열에서 갯수를 센다고 하면 Brute force, HashMap, Sorting방법을 생각해보자.

10. 만약에 대다수를 구하는 문제라면 Boyer–Moore majority vote algorithm를 생각해보자.

11. Arrays 디버깅할때 Arrays.stream(nums).boxed().forEach(System.out::println);하면 결과를 볼수 있다.

12. 순서, 부호를 이용해서 공간을 절약할 수 있는지 생각해본다.

13. 간단한것 부터 생각해본다. 배열이 있다면 인덱스를 양방향으로 사용하기보다는 한방향으로 사용해보고 정안되면 양방향으로 생각을 바꿔보자. 간단하게 생각하고 간단하게 문제를 만들줄 알아야한다.

14. 값을 원하는지 요소를 원하는지 확인해라. 일반적으로 값을 구하는게 더 간단하게 풀 수 있다.