Balanced Binary Tree - LeetCode

문제 접근 🤔

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

이진 트리에서 높이 균형이란, 각 서브 트리의 높이 차이가 1 이하인 상태를 말한다. 즉, 트리의 각 서브 트리에 대해 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하여야 한다.

• 주어진 이진 트리가 높이 균형이 맞는지 확인하는 문제
• DFS를 통해 트리의 가장 하단부터 트리를 타고 올라가면서 각 노드의 높이를 반환하자.
• 노드의 왼쪽 노드와 오른쪽 노드의 높이 차이가 1보다 크다면 높이 균형이 맞지 않는 이진 트리이므로 False를 저장하고 모든 노드의 높이 차이가 1 이하라면 True를 저장하여 이를 최종 반환해주면 된다.

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(56 ms)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.isHeightBalanced = True

        def dfs(node, height = 0):
            if not node:
                return height
            height += 1
            left, right = dfs(node.left, height), dfs(node.right, height)
            if abs(left - right) > 1:
                self.isHeightBalanced = False
            return max(left, right)

        dfs(root)
        return self.isHeightBalanced

자바스크립트 코드(76 ms)

const isBalanced = (root) => {
  let isHeightBalanced = true;

  const dfs = (node, height = 0) => {
    if (!node) {
      return height;
    }
    height++;
    let [left, right] = [dfs(node.left, height), dfs(node.right, height)];
    if (Math.abs(left - right) > 1) {
      isHeightBalanced = false;
    }
    return Math.max(left, right);
  };
  dfs(root);
  return isHeightBalanced;
};