LeetCode 노트: 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 depth of the two subtrees of every node never differ by more than 1.

대의:

두 갈래 나무를 주어 높이가 균형이 맞는지 아닌지를 판단하다.이 문제에 대해 고도로 균형이 잡힌 두 갈래 나무는 각 노드의 두 개의 자 노드의 깊이 차이가 1을 넘지 않는 두 갈래 나무를 가리킨다.

생각:

이 문제의 제목은 너무 간략하게 말해도 예가 없다. 끊임없이 잘못 시험해 낸 상황에 따라 각 노드의 두 자노드의 깊이는 1보다 크다고 할 수 없다. 예를 들어 왼쪽 자노드 아래에 자노드가 있고 오른쪽 자노드 아래에 없다. 이것은 허용된 것이다. 깊이는 1이다. 그러나 왼쪽 자노드의 자노드에 자노드가 있다면 깊이의 차이는 2이고 불균형적이다.
만약 하위 노드가 있는지 없는지를 직접 판단한다면, 상황이 너무 많아서 하기 어렵다.차라리 각 노드의 깊이를 직접 귀속해서 기록한 다음에 각 노드의 두 하위 노드의 깊이의 차이가 1보다 큰지 비교하는 것이 낫다.
여기에 각 하위 노드의 깊이를 기록하려면 귀속적인 방법으로 잎 노드의 깊이가 1이고 위로 점차적으로 증가해야 한다. 귀속적으로 하나의 노드의 깊이를 계산할 때 왼쪽 노드와 오른쪽 노드의 깊이가 어느 것이 더 깊은지 판단하고 더 깊은 것, 즉 수치가 더 큰 것을 취해야 한다.
그리고 각 노드의 좌우 서브노드의 깊이 차이가 1보다 큰지 아닌지를 판단할 수 있다.그러나 모든 노드를 다시 한 번 훑어봐야 시간이 늘어난다.위에서 우리가 각 노드의 깊이를 계산할 때 한 걸음은 좌우 노드의 어느 노드가 더 깊은지 판단하는 것이다. 여기서 차이가 1보다 큰지 직접적으로 비교할 수 있다. 만약에 1보다 크면 우리는 이 노드의 깊이를 -1로 특수하게 기록한다. 이것은 나타나지 않는 깊이값이다. 우리는 맨 윗층으로 전달하여 제목이 두 갈래 나무가 불균형하다는 것을 알려주기를 바란다. 따라서 각 노드의 좌우 노드를 계산할 때좌우 노드의 깊이가 -1과 같은지 아닌지를 판단해야 한다. 만약 있다면 아래에 불균형이 생겼다는 것을 설명한다. 이때 -1이라는 신호를 직접 업로드하면 된다.이렇게 층층이 루트로 돌아가면 루트 노드의 깊이가 -1인지 아닌지에 따라 균형이 맞는지 판단할 수 있다.

코드(Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (height(root) == -1) return false;
        else return true;
    }
    
    public int height(TreeNode root) {
        if (root == null) return 0;
        else {
            int leftHeight = height(root.left);
            if (leftHeight == -1) return -1;
            int rightHeight = height(root.right);
            if (rightHeight == -1) return -1;
            if (leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1) return -1;
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

집합:https://github.com/Cloudox/LeetCode-Record
작성자 홈페이지 보기