[Leetcode] 110. Balanced Binary Tree

1. 문제링크

Balanced Binary Tree - LeetCode

 

2. height-Balanced가 뭐지?

여기서 파란색 볼드를 클릭하면 height-balanced에 대한 설명이 나온다

 

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.

 

즉 모든 노드에 대해서, 좌우subtress간의 높이 차가 1보다 작거나 같은 트리이다

 

위에서 root node인 3을 보면

왼쪽 subtree의 높이는 0 (9에서 더 뻗어나가는게 없으므로)

오른쪽 subtree의 높이는  1 (20이 오른쪽 subtree의 끝 노드가 아니므로)

1 - 0 = 1이니 height-balanced가 맞다

 

 

root node인 1에 대해서

왼쪽 subtree 높이 : 2, 오른쪽 subtree 높이 : 0 이므로

2 - 0 > 1이니 height-balanced가 아니다

 

 

3. Solution

class Solution {
public:
    bool result = true;
    int solve(TreeNode* root){
        if(!root || result == false)
            return 0;
        
        int left = solve(root->left);
        int right = solve(root->right);
        if(abs(left - right) > 1){
            result = false;
            return 0;
        }        
        return max(left, right) + 1;
    }
    bool isBalanced(TreeNode* root) {
        solve(root);
        return result;
    }
};