[LeetCode] 563. Binary Tree Tilt

https://leetcode.com/problems/binary-tree-tilt/

Binary Tree Tilt - LeetCode

Binary Tree Tilt - Easy

 

binary tree에서 각각의 노드의 tilt의 합을 구하는 문제다.

노드의 tilt란 왼쪽 모든 하위노드들의 합과 오른쪽 모든 하위노드들의 합의 차이를 의미한다.

 

먼저 최하위 노드로 가서 결과값에 0을 더해준다. (최하위는 자식노드들이 없으므로)

그 다음, 그 위 노드로 가서 양쪽 노드의 값을 해당 노드에 더해주고, tilt를 구해 결과값에 더해준다.

그리고 또 위 노드로 가서 해당작업을 반복한다.

즉, 아래부터 계산이 이뤄져야 한다.

 

전체 풀이 코드

class Solution {
public:
    int s=0;
    int findTilt(TreeNode* root) {
        run(root);
        return s;
    }
    void run(TreeNode* node) {
        if (!node) return;
        run(node->left);
        run(node->right);
        int l=0, r=0;
        if (node->left) node->val += node->left->val, l=node->left->val;
        if (node->right) node->val += node->right->val, r=node->right->val;
        s += abs(l-r);
    }
};