[Easy] 110. Balanced Binary Tree

문제

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as

: a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

 

이진 트리가 주어지면 높이 균형이 맞는지 확인합니다.

이 문제에서 높이 균형 이진 트리는 다음과 같이 정의됩니다.

: 모든 노드 의 왼쪽 및 오른쪽 하위 트리의 높이가 1 이하로 다른 이진 트리.

예시

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: true

 

제약 조건

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

 

해결 과정

• getHeight라는 함수를 이용하여 dfs 방법을 사용한다.
  • node가 undefined거나 null이 들어오면 0을 반환한다.
  • left와 right 각각 getHeight 함수를 재귀 호출한다. 이때 1을 각가 더해 level을 하나씩 증가시킨다.
  • 만약 left와 right의 차이가 1보다 크다면 Infinity를 반환한다.
  • 1보다 크지 않다면 left와 right 값 중 더 큰 값을 반환한다.
• getHeight의 반환값을 answer 변수로 받는다.
• answer가 Infinity라면 false를, 아니라면 true를 반환한다.

해결 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    
    const getHeight = (node) => {
        if(!node) return 0;
        
        let left = getHeight(node.left) + 1;
        let right = getHeight(node.right) + 1;
        
        if(Math.abs(left - right) > 1) return Infinity;
        
        return Math.max(left, right)
    }
    
    let answer = getHeight(root)
    return answer !== Infinity ? true : false
};