Diameter of Binary Tree: Recursion (DFS)**

First Thoughts: better to split into smaller subproblems. The way of actually getting the answer requires some time (think about how solutions are reached, generally). 하나하나의 루트를 기준으로 diameter (longest path)는 그냥 그 루트를 지난다고 가정을 한다. 그리고 그 sub-diameter값을 left, right, 그리고 current와 비교하여 최댓값을 택한다. 한 루트를 기준으로 longest path는 left에서의 maxHeight + right에서의 maxHeight이다.

My First Solution:

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        fillMaxArrays(root, list);
        return Collections.max(list);
    }
    
    public void fillMaxArrays(TreeNode root, ArrayList<Integer> max) {
        if (root==null) return;
        max.add(maxPath(root.left));
        max.add(maxPath(root.right));
        fillMaxArrays(root.left, max);
        fillMaxArrays(root.right, max);
        
    }
    
    public int maxPath(TreeNode root) {
        int counter = 1;
        ArrayList<Integer> leftHeights = new ArrayList<>();
        ArrayList<Integer> rightHeights = new ArrayList<>();
        if (root==null) return 0;
        getHeight(root.left, counter, leftHeights);
        getHeight(root.right, counter, rightHeights);
        int leftMaxPath = 0;
        int rightMaxPath = 0;
        if (!leftHeights.isEmpty()) leftMaxPath = Collections.max(leftHeights);
        if (!rightHeights.isEmpty()) rightMaxPath = Collections.max(rightHeights);
        int maxPath = leftMaxPath+rightMaxPath;
        return maxPath;
    }
    
    public void getHeight(TreeNode root, int counter, ArrayList<Integer> list) {
        if (root==null) return;
        if (root.left==null && root.right==null) {
            list.add(counter);
        }
        getHeight(root.right, counter+1, list);
        getHeight(root.left, counter+1, list);
        
    }
}

My Second (Improved) Solution:

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        int leftMaxPath = diameterOfBinaryTree(root.left);
        int rightMaxPath = diameterOfBinaryTree(root.right);
        int bigger = Math.max(leftMaxPath, rightMaxPath);
        int currentMaxPath = getMaxHeight(root.left, 1) + getMaxHeight(root.right, 1);
        return Math.max(bigger, currentMaxPath);
    }
    public int getMaxHeight(TreeNode root, int count) {
        if (root==null) return 0;
        if (root.left==null && root.right==null) return count;
        int leftCount = getMaxHeight(root.left, count+1);
        int rightCount = getMaxHeight(root.right, count+1);
        return Math.max(leftCount, rightCount);
    }
}

Catch Point:

1. 글로벌 변수를 안쓰려고 한 것은 좋은 도전이었다고 생각하지만, 그의 substitute로 arrayList는 좋은 대안이 아니었던 것 같다. 우리는 최댓값만 신경 쓴다 (그래서 계속 최댓값을 업데이트하는 방식으로 가야한다.)

2. root==null 일때를 handle해줘야 한다.

3. 큰 문제에서만 차근차근 변수명을 붙여서 풀어주면 생각보다 쉽게 풀린다. Recursion은 그 sub변수들이 된다고 믿어야 한다.

4. Helper Method가 2개 이상 넘어가면 강한 의심을 해야한다. 보통 절대 3개 이상을 쓰는 문제는 안나오는 것 같다 (그럼 문제를 너무 어렵게, 세세하게 생각하고 있다는 뜻이다.)