[Leetcode] 563. Binary Tree Tilt

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

---

이진 트리 루트가 주어지면 모든 트리 노드의 기울기 합을 구하라.

트리 노드의 기울기는 모든 왼쪽 하위트리 노드들의 합, 모든 오른쪽 하위 트리 노드들의 합들 차이의 절대값이다. 만일 하위트리가 없으면 합을 0으로 본다. 

---

정답 전역변수를 하나 두고 왼쪽, 오른쪽 하위트리를 탐색하며 합들을 구한 뒤, 왼쪽 오른쪽 노드들의 합 차이의 절대값을 정답 변수에 더해나간다. 그리고 왼쪽, 오른쪽 자식 노드들의 합 + 현재 노드의 val을 더한 값을 반환한다. 

정답 = 0

func getSum(node) {
	if(node == NULL) return 0
	left = getSum(node->left)
    right = getSum(node->right)
    
    정답 += |left - right|
    return left + right + node->val
}

func findTilt(root) {
	getSum(root)
    return 정답
}

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/563.%20Binary%20Tree%20Tilt.cpp