(C++) - LeetCode (easy) 110. Balanced Binary Tree

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

Balanced Binary Tree - LeetCode

자료구조 문제였습니다.

📕 풀이방법

📔 풀이과정

tree의 높이를 구하는 getHeight 함수와, 균형 여부를 판단하는 isBalanced 함수를 구현해줍니다.

1. getHeight함수 

tree 의 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 호출해 높이를 구합니다.

2. isBalanced

마찬가지로 왼쪽, 오른쪽 자식에 대해 재귀함수를 수행합니다. 왼쪽 자식과 오른쪽 자식 높이 차이를 diff에 저장해주고 차이가 1초과라면 false를 아니라면 min값을 반환해줍니다.

---

📕 Code

📔 C++

/**
 * 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;
        return max(getHeight(node->left), getHeight(node->right)) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        int diff = abs(getHeight(root->left) - getHeight(root->right));
        if(diff > 1) return false;
        return min(isBalanced(root->left), isBalanced(root->right));
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.