563 : Binary Tree Tilt ( leetcode / java )

*해결과정

 

  불쌍한 문제입니다. ㅜㅜ 비추수가 압도적으로 많습니다. 일반적인 tree의 문제가 아니라 그런 것 같습니다. 최근에 풀었던 파x 기업의 3번문제와 비슷합니다. postOrder 형식의 처리가 필요합니다. 즉, leaft쪽으로 먼저 이동해 root의 왼쪽 자식과 오른쪽 자식의 값을 계산하여 계속 부모쪽으로 올라오면서 최신화를 시켜주면 됩니다. 우리는 Tilt의 값을 찾으면 되기 때문에 굳이 TreeNode의 root값들을 최신화 시켜 줄 필요는 없습니다.

 

class Solution {
    
    int totalTilt=0;
    
    public int findTilt(TreeNode root) {
        valueSum(root);
        return totalTilt;
    }
    
    public int valueSum(TreeNode root){
        if(root==null) return 0;
        
        int leftSum = valueSum(root.left);
        int rightSum = valueSum(root.right);
        totalTilt += Math.abs(leftSum-rightSum);
        return leftSum + rightSum + root.val;
    }
}