LeetCode(110) Balanced Binary Tree

2167 단어

제목


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보다 작아야 하며, 좌우 자목의 높이를 요구하기만 하면 비교 판정하면 된다.

AC 코드

class Solution {
public:
    // 
    bool isBalanced(TreeNode* root) {
        if (!root)
            return true;

        int lheight = height(root->left), rheight = height(root->right);

        if (abs(lheight - rheight) <= 1)
            return isBalanced(root->left) && isBalanced(root->right);
        else
            return false;
    }
    // 
    int height(TreeNode *root)
    {
        if (!root)
            return 0;
        else
            return max(height(root->left), height(root->right)) + 1;
    }
};

GitHub 테스트 프로그램 소스

좋은 웹페이지 즐겨찾기