110. Balanced Binary Tree [Easy]

https://leetcode.com/problems/balanced-binary-tree/

Balanced Binary Tree - LeetCode

 

이진 트리가 주어졌을 때, 균형 트리(왼쪽 서브트리와 오른쪽 서브트리의 높이가 2이상 차이나지 않는 트리)를 만족하는지 확인하는 문제다.

간단히 생각했을 때는 양측 최대 깊이를 구해서 루트에서 비교했더니 아래와 같은 조건에서 문제가 됐다.

매 노드마다 검사를 진행해서 결과를 도출해낸다.

문제가 됐던 조건

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int calculDepth(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        int left = calculDepth(node->left);
        int right = calculDepth(node->right);
        if (abs(left - right) > 1 || left == -1 || right == -1) {
            return -1;
        }
        
        return 1 + max(left, right);
    }
    bool isBalanced(TreeNode* root) {
        if (calculDepth(root) == -1) {
            return false;
        }
        else {
            return true;
        }
    }
};