[LeetCode] 밸런스 바이너리 트리 밸런스 트리

1155 단어 LeetCode
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) 좌우 나무는 모두 균형수이고, 2) 왼쪽 나무와 오른쪽 나무의 높이 차이는 1보다 작다.다음은 코드입니다.
    bool isBalanced(TreeNode *root) {
        int leftH, rightH;
        return isBalancedUtil(root, leftH, rightH);
    }
    
    bool isBalancedUtil(TreeNode* root, int& leftH, int& rightH)
    {// utility function
        if(root == NULL)
        {
            leftH = 0;
            rightH = 0;
            return true;
        }
        
        int leftH1, rightH1, leftH2, rightH2;
        if(! isBalancedUtil(root->left, leftH1, rightH1) )
            return false;
        if(! isBalancedUtil(root->right, leftH2, rightH2) )
            return false;
        
        leftH = max(leftH1, rightH1) + 1;
        rightH = max(leftH2, rightH2) + 1;
        if(abs(leftH-rightH)>1)
            return false;
        else
            return true;
    }

좋은 웹페이지 즐겨찾기