[ leetcode ] 110. Balanced Binary Tree

Binary Tree가 주어졌을 때, 해당 트리가 균형 잡힌 트리인지를 확인하는 문제입니다.

균형 잡힌 트리는 서로 다른 노드를 루트 노드로 하는 서브 트리 사이에 높이 차이가 1이하인 노드들로 구성된 트리를 의미합니다.

마찬가지로 재귀를 이용하여 left, right child로 시작하는 서브 트리의 균형 여부를 확인하고, 해당 노드의 균형 여부는 각 left, right child subtree의 depth를 구하여 판단합니다.

/**
 * 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) {}
 * };
 */
#define max(a,b)((a) > (b) ? (a) : (b))

class Solution {
public:
    int findDepth(TreeNode* root) {
    	if (!root) return 0;
        int left = findDepth(root->left);
        int right = findDepth(root->right);
        return 1 + max(left, right);
    }
    
    bool isBalanced(TreeNode* root) {
    	if (!root) return true;
        bool left_balanced = isBalanced(root->left);
        bool right_balanced = isBalanced(root->right);
        if (!left_balanced || !right_balanced) return false;
        
        int left_depth = findDepth(root->left);
        int right_depth = findDepth(root->right);
        int diff = left_depth > right_depth ? left_depth - right_depth : right_depth - left_depth;
        if (diff > 1) return false;
        return true;
    }
};