treecode

public int getMax(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int leftVal = Math.max(0, getMax(node.left));
    int rightVal = Math.max(0, getMax(node.right));

    max = Math.max(max, node.val + leftVal + rightVal);

    return node.val + Math.max(leftVal, rightVal);
}

이어진 노드중 가장 큰 값을 구하는 문제로 먼저 재귀 호출을 계속 하면서 트리 끝까지 이동한다.

끝에서부터 음수인 값(leftVal, rightVal)은 더하지 않고 양수인 값만 더해간다.

반환하기 전에 해당 노드 기준으로 max 값을 갱신

자식 노드가 양수더라도 부모 노드 음수 값이 더 크면 해당 노드는 짤린다.

중간에 아니다 싶을때 뚫린 구멍 막는 식으로 풀지 말고 다시 생각해보기..!

부모 노드와 자식 노드 값 차이의 절대값중 가장 큰 값을 구하는 문제로 Map<Integer, List<Integer>> 를 만들어서 노드마다 자식 노드 값을 저장했더니 효율성이 처참하게 나왔다. 

public void DFS(TreeNode node, int max, int min) {
    if (node == null) {
        return;
    }
    int newMax = Math.max(max, node.val);
    int newMin = Math.min(min, node.val);

    answer = Math.max(answer, Math.abs(newMax - newMin));

    DFS(node.left, newMax, newMin);
    DFS(node.right, newMax, newMin);
}

최대값, 최소값을 갱신하면서 재귀로 호출하면 현재 노드부터 최상위 노드중 최대값, 최소값의 차이를 구하기 때문에 노드마다 일일이 계산할 필요가 없다.