[BinaryTree][Easy] 110. Balanced Binary Tree

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

 

주어진 이진트리가 balanced binary tree인지 판단하라. 

 

balanced 이진트리가 정확하게 무엇인지 먼저 재정의 해 보자.

 

특정 노드 기준으로 depth차가 최대 1이어야 한다. 

다음 그림에서 dv 가  특정 노드에서 depth차를 의미한다.

 

 

아래 노드는 B 노드가 dv 2로 만족하지 않는다.

 

 

따라서 특정 노드에서 양 child 최대 depth를 구하고 그 차가 1보다 같거나 작은지 판단한다.

 

 

코드.

int isBalancedDFS(bool& isBalanced, TreeNode* node)
{
    if (!isBalanced)
        return isBalanced;

    if (node == nullptr)
        return 0;

    int left = 1 + isBalancedDFS(isBalanced, node->left);
    int right = 1 + isBalancedDFS(isBalanced, node->right);

    if (abs(left - right) > 1)
    {
        isBalanced = false;
        return 0;
    }
    return max(left, right);
}

bool isBalanced(TreeNode* root) 
{
    bool ret = true;
    isBalancedDFS(ret, root);
    return ret;
}

 

 

 

결과