•
•
문제 설명 : 문제에 작성된 조건에 따라 하위노드를 연산하고 연산된 노드들의 값 합을 구한다.
•
풀이 방법
◦
중요한점은 누적 합산과 하위 트리 계산을 따로 해야한다는 점이다.
◦
A노드가 있으면, A의 좌/우 노드의 차이를 절대 값으로 구한게 A노드의 값이다.
◦
단 자식 노드가 있는 이 값들은 별도의 값에 누적해줘야한다.
◦
좌/우 노드의 차이로 설정된 노드로 이후 연산을 하지 않기 때문이다.
•
시간복잡도 :
•
성공 코드
# 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:
result = 0
def findTilt(self, root: Optional[TreeNode]) -> int:
self.result = 0
def search_tree(node):
# left 노드일 경우 바로 반환
if not node.left and not node.right:
return node.val
# 좌/우 노드 값 확인
left = search_tree(node.left) if node.left else 0
right = search_tree(node.right) if node.right else 0
# 전체 결과에 합산
self.result += abs(left - right)
# 하위 합산 반환
return left + right + node.val
if root:
search_tree(root)
return self.result
Python
복사