110. Balanced Binary Tree

출처: https://leetcode.com/problems/balanced-binary-tree/

Balanced Binary Tree - LeetCode

 

문제

 

이진 트리가 균형잡힌 트리인지 판단하라.

 

이 문제에서, 균형잡힌 트리란:

트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1이하인 이진트리

 

예제

Input: root = [3,9,20,null,null,15,7]
Output: true

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

 

풀이

 

트리 탐색 알고리즘인 DFS를 사용하여 풀 수 있는 문제

 

다음 코드는 DFS 방식으로 트리의 높이를 구하는 코드이다.

function dfs(root) {
	if (root.isLeaf()) { return 0; }
    
	const left = root.left != null ? dfs(root.left) + 1 : 0;
	const right = root.right != null ? dfs(root.right) + 1 : 0;
    
	return Math.max(left, right)
}

이 DFS 코드는 트리의 높이만을 계산할 뿐, 균형잡힌 트리인지를 판단하진 않는다. 그렇기 때문에 이 코드에 균형잡힌 트리인지 판단하기 위한 코드를 작성해야 한다.

 

DFS를 통해 트리 높이를 계산하기 위해 왼쪽 자식과 오른쪽 자식의 높이를 계산한다는 것을 볼 수 있는데, 이때 두 자식 노드의 비교를 통해 원하는 답을 얻을 수 있다.

let answer = true;

function dfs(root) {
	if (root.isLeaf()) { return 0; }
    
	const left = root.left != null ? dfs(root.left) + 1 : 0;
	const right = root.right != null ? dfs(root.right) + 1 : 0;
    
	if (Math.abs(left - right) > 1) { answer = false; }
    
	return Math.max(left, right)
}

 

Github = 110.js

opwe37/Algorithm-Study