[알고리즘] LeetCode Balanced Binary Tree JS

개요

 

주어진 이진 트리가 균형 이진 트리인지 확인하는 문제이다

Balanced Binary Tree - LeetCode

 

 

풀이

균형이진트리가 뭐였는지 헷갈려서 정리를 간단히 해보았다.

 

우선 단순한 이진트리는 아래와 같다

높이(height)가 3인 이진트리

 

 

하지만 트리 중에서 한쪽으로 치우쳐진 트리들이 있는데 편향 이진 트리라고도 하며 만약 탐색한다고 할때 트리의 장점을 살리지 못하고

모든 노드를 방문해야한다는 문제가 생긴다.

https://www.quora.com/What-is-a-skewed-tree

 

 

따라서 균형 이진 트리라고해서 모든 노드마다 노드별 왼쪽 서브 트리(왼쪽의 모든 노드)와 오른쪽 서브 트리(오른쪽의 모든 노드) 갯수의 차이가 1이하로 설정된 트리를 말한다. AVL트리라고도 하며 균형을 맞추기 위해 회전시키기도 하는데 기본적인 자료구조라서 따로 정리하진 않고 문제로 넘어갔다.

 

 

DFS탐색으로 문제를 푸는데 bottom up 방식으로 맨 아래있는 노드의 높이부터 확인해보며 넘어온다.

단순히 일반적인 DFS 탐색이며 높이를 전달해준다고 이해하면 될거같다.

 

만약 균형이 맞지않는다는 것을 확인하면 그냥 Infinity속성을 활용하여 값을 넘기게 된다

/**
 * 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}
 *
 *
 * balanced binary tree란 각 루트노드마다 왼쪽 오른쪽 노드의 높이 차이가 1이하인 경우를 말한다
 */
var isBalanced = function (root) {
  if (!root) return true;

  const DFS = (node) => {
    if (node === null) return 0;
    const left = DFS(node.left);
    const right = DFS(node.right);
    if (Math.abs(right - left) > 1) return Infinity;
    return Math.max(left, right) + 1;
  };

  return DFS(root) !== Infinity ? true : false;
};