이진 트리 기울기

이진 트리의 root가 주어지면 모든 트리 노드 기울기의 합을 반환합니다.

트리 노드의 기울기는 모든 왼쪽 하위 트리 노드 값과 모든 오른쪽 하위 트리 노드 값의 합계 간의 절대 차이입니다. 노드에 왼쪽 자식이 없으면 왼쪽 하위 트리 노드 값의 합계가 0 로 처리됩니다. 노드에 오른쪽 자식이 없는 경우에도 규칙은 비슷합니다.

예 1:



입력: 루트 = [1,2,3]
출력: 1
설명:
노드 2의 기울기 : |0-0| = 0(자식 없음)
노드 3의 기울기 : |0-0| = 0(자식 없음)
노드 1의 기울기: |2-3| = 1(왼쪽 하위 트리는 왼쪽 자식이므로 합계는 2이고 오른쪽 하위 트리는 오른쪽 자식이므로 합계는 3입니다.)
모든 기울기의 합 : 0 + 0 + 1 = 1

예 2:



입력: 루트 = [4,2,9,3,5,null,7]
출력: 15
설명:
노드 3의 기울기 : |0-0| = 0(자식 없음)
노드 5의 기울기 : |0-0| = 0(자식 없음)
노드 7의 기울기 : |0-0| = 0(자식 없음)
노드 2의 기울기 : |3-5| = 2(왼쪽 하위 트리는 왼쪽 자식이므로 합계는 3이고 오른쪽 하위 트리는 오른쪽 자식이므로 합계는 5입니다.)
노드 9의 기울기: |0-7| = 7(왼쪽 자식이 없으므로 합계는 0, 오른쪽 하위 트리는 바로 오른쪽 자식이므로 합계는 7)
노드 4의 기울기 : |(3+5+2)-(9+7)| = |10-16| = 6(왼쪽 하위 트리 값은 3, 5 및 2이며 합계는 10이고 오른쪽 하위 트리 값은 9 및 7이며 합계는 16입니다.)
모든 기울기의 합 : 0 + 0 + 0 + 2 + 7 + 6 = 15

예 3:



입력: 루트 = [21,7,14,1,1,2,2,3,3]
출력: 9

제약:

트리의 노드 수가 [0, 104] 범위에 있습니다.

-1000 <= Node.val <= 1000

해결책:

# 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 sumOfTree(self, root):
        if root:
            return root.val + self.sumOfTree(root.left) + self.sumOfTree(root.right)
        return 0

    def findTilt(self, root: Optional[TreeNode]) -> int:
        if root:
            l = self.sumOfTree(root.left)
            r = self.sumOfTree(root.right)
            return abs(l - r) + self.findTilt(root.left) + self.findTilt(root.right)
        else:
            return 0