563. Binary Tree Tilt

[zeikar]

Problem link

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

Problem Summary

이진트리에서 모든 노드의 tilt 값의 합을 구하는 문제.
tilt는 자신 왼쪽 서브트리의 합과 오른쪽 서브트리의 합의 절대값 차이다.

Solution

그냥 재귀적으로 tilt를 계속 구해주면 된다.
노드의 합 + 노드의 tilt 해서 2개를 배열로 관리해주며 돌려준다.

Source Code

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        return self.solve(root)[1]

    def solve(self, root: Optional[TreeNode]) -> [int, int]:
        if root is None:
            return 0, 0

        left_sum, left_tilt = self.solve(root.left)
        right_sum, right_tilt = self.solve(root.right)
        return left_sum + right_sum + root.val, abs(left_sum - right_sum) + left_tilt + right_tilt