(Leet Code c++)Balanced Binary Tree

110. Balanced Binary Tree

 

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.

 

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

 

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

주어진 트리가 균형 이진 트리인지 확인하는 문제.

getHeight() 함수로 트리의 왼쪽 자식의 height와 오른쪽 자식의 height를 구한다.

재귀를 통해 left와 right의 차이가 1이 나지 않으면서, 왼쪽 자식의 노드가 균형이 맞춰져 있고, 오른쪽 자식의 노드 또한 균형이 맞춰져 있다면 true를 반환.

그렇지 않다면 false를 반환한다.

 

재귀가 있기 때문에 헷갈릴 수 있지만, 천천히 따라가면 충분히 풀 수 있는 문제.

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