솔루션 개발:

질문

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.

예시:

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

질문 설명

이 질문의 등급은 쉬움입니다. 대부분 정확합니다. 나는 이 질문이 해결하기 쉽다고 믿지 않는다. 이 문제를 해결하려면 몇 가지 기술과 패턴을 알아야 합니다.

이 질문은 Maximum Depth of Binary Tree 에 매우 가깝습니다. 이 경우 모든 노드에서 모든 하위 트리의 높이를 추적해야 하므로 '왼쪽 또는 오른쪽 트리의 높이가 1만큼 다른가요?'라는 질문을 할 수 있습니다.

Leetcode가 우리에게 요청한 것은 트리가 높이 균형을 이루고 있는지 확인하는 것입니다. 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 1 이하로 다른 이진 트리입니다.

권장 지식

Binary Tree

Depth First Search

Post Order Traversal

Maximum Depth of Binary Tree

Recursive Depth First Search

우리는 무엇을 알고 있습니까?

이진 트리가 있습니다(대부분 비어 있을 수 있음)

모든 노드의 왼쪽 및 오른쪽 하위 트리 높이를 찾아야 합니다.

어떻게 할 것인가:

Post Order Traversal을 사용하여 모든 노드의 왼쪽 및 오른쪽 하위 트리 높이를 찾을 것입니다. 각 하위 트리에 높이 매개변수를 전달하고 트리의 맨 아래에 도달할 때까지 걸리는 노드 수를 세어 이를 수행합니다. 최하위 노드에 도달하면 트리의 높이를 찾았다는 의미입니다.

이제 우리는 왼쪽 및 오른쪽 하위 트리의 높이를 알고 있습니다. 이제 우리가 할 일은 '내 왼쪽 나무와 오른쪽 나무의 높이가 1만큼 차이가 나는가?'라고 묻는 것뿐입니다. 그들 중 하나라도 이를 위반하면 플래그를 거짓으로 설정합니다.

aflag를 true로 설정합니다. 따라서 기본적으로 트리가 높이 균형을 이룬다고 가정합니다. 이를 위반하는 노드를 찾을 때까지 플래그를 false로 설정합니다.

트리의 사후 순회를 수행합니다. 각 노드에 height 매개변수를 전달합니다.

각 노드의 왼쪽 및 오른쪽 높이를 제공합니다.

'내 왼쪽 또는 오른쪽 나무의 높이가 1만큼 차이가 나나요?'라는 질문을 합니다. 그들 중 하나라도 이를 위반하면 플래그를 거짓으로 설정합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 트리 내의 모든 노드를 순회할 것입니다.

공간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 최악의 경우와 마찬가지로 트리의 전체 높이를 호출 스택에 저장해야 합니다.

리트코드 결과:

제출 링크 참조:

런타임: 70ms, Balanced Binary Tree

에 대한 JavaScript 온라인 제출의 95.74%보다 빠름

메모리 사용량: 47.1MB, Balanced Binary Tree

에 대한 JavaScript 온라인 제출의 63.74% 미만

해결책

/**
 * 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) {

    // A flag to check if the tree is balanced or not
    let flag = true;

    // Helper function to check if the tree is balanced or not
    const get_heights = (node, height) => {

        // Empty tree? It's 0 in height
        if (!node) {
            return 0;
        }

        // Get my left and right heights
        // by adding 1 to the height of the left and right subtrees.
        // each time we move down them
        const left_height  = get_heights(node.left, height + 1);
        const right_height = get_heights(node.right, height + 1);

        // Let's use some math.
        // Technically, if we have a balanced tree, the difference
        // should always be 0. But because, this question is awkward, we need to check if 
        // if its diff is greater than 1. So we minus the two by using absolutes values and asking
        // if the diff in this sub tree was greater than 1. If so bad un balanced.
        if (Math.abs(right_height - left_height) > 1) {
            flag = false;
        }

        // Return the height of the tree
        // By returning whoever had the bigger height and adding 1 (Our current node)
        return Math.max(left_height, right_height) + 1;
    };

    // Call the helper function
    get_heights(root, 0);

    // Get the flag back to base. :D
    return flag;
};