110. Balanced Binary Tree | LeetCode 문제 풀이

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

Balanced Binary Tree - 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 left and right subtrees of every node differ in height by no more than 1.

 

-> 주어지는 binary tree가 AVL tree 성질에 맞는지 검사한 후 이를 bool 타입으로 return

 

예제

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

 

 

---

 

* 재귀함수 구현이 쉽지 않아 해당 문제의 풀이가 올라온 블로그의 글을 참고하여서 코드의 구조가 유사하다.

참고한 블로그 - https://hackmd.io/@Zero871015/LeetCode-110

【LeetCode】 110. Balanced Binary Tree - HackMD

 

 

풀이

• getHeight (: int) 함수를 새로 만들고 해당 노드의 height를 return 하도록 하였다
• isBalanced 함수를 이용하여  현재 root 노드의 왼쪽 자식과 오른쪽 자식의 height를 구하고 둘의 차를 구하여 절댓값이 1보다 클 경우 false를 return, 아닐 경우 현재 root 노드의 왼쪽 자식과 오른쪽 자식으로 내려간 후 isBalanced 함수를 이용한 비교를 다시 진행한다.

/**
 * 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 getHeight(TreeNode* node) {
        if (node == NULL) return 0;
        int l = getHeight(node->left);
        int r = getHeight(node->right);
        return ((l > r) ? l : r) + 1;
    }
    
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int hLeft = getHeight(root->left);
        int hRight = getHeight(root->right);
        if (((hLeft-hRight)>1) || ((hLeft-hRight)<-1)) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

 

특이점

처음에 getHeight 함수를 아래와 같이 짰더니 Time Limit Exceeded 에러가 났다.

 

int getHeight(TreeNode* node) {
    if (node == NULL) return 0;
    return (getHeight(node->left) > getHeight(node->right)) ? (getHeight(node->left) + 1) : (getHeight(node->right) + 1);
}

 

 

결과 자체는 내 해답과 같지만 시간이 너무 오래 걸리는 코드였다.

 

 

원인

return (getHeight(node->left) > getHeight(node->right)) ? (getHeight(node->left) + 1) : (getHeight(node->right) + 1);

return (조건식) ? (A) : (B);

 

time error가 난 코드의 조건식에서 대소 비교를 할 때 getHeight 함수를 두번 호출하는데, 그 후 A 또는 B를 값으로 내뱉을 때도 getHeight 함수가 호출된다. 심지어 재귀함수로 구현했으니... 트리에 있는 노드의 값이 많아질 수록 time 또한 기하급수적으로 증가해 error가 나게 되는 것이다.

 

쓸데없이 다중으로 함수가 호출되는 문제를 해결하기 위해 다음과 같이 코드를 수정하여 해결하였다.

 

int getHeight(TreeNode* node) {
    if (node == NULL) return 0;
    int l = getHeight(node->left);
    int r = getHeight(node->right);
    return ((l > r) ? l : r) + 1;
}

 

재귀함수에 대해 더 공부하고... 문제도 많이 풀어봐야 할 것 같다.

 

 

+) 수업시간 풀이

 

/**
 * 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 height(TreeNode* node){
        if (node == NULL) return -1;
        if (node->keft == NULL && node->right == NULL) return 0;
        return 1 + max(height(node->left), height(node->right));
    }
    bool isBalanced(TreeNode* root){
        if(root == NULL) return true;
        return (abs(height(root->left) - height(root->right)) <= 1) && isBalanced(root->left) && isBalanced(root->right);
    }
};