[LeetCode Road] Balanced Binary Tree - Solution/C++

110. Balanced Binary Tree

Question:

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:

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

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

Input: root = []
Output: true

Constraints:

TThe number of nodes in the tree is in the range [0, 5000].

-10^4 <= Node.val <= 10^4

Source code

Version 1

Idea:
We can calculate the depth of subnodes and use it to compare. How to get calculate the depth for binary tree? You can refer to Maximum Depth of Binary Tree.

So, declare a getDepth() function to implement the depth of binary tree. At 18 line, abs(left_depth - right_depth) > 1 is based on a rule of height-balanced binary tree.

Time complexity: O(n)
// n: the total of nodes Space complexity: O(H) // H: the height of tree

/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int left_depth = getDepth(root->left);
        int right_depth = getDepth(root->right);
        if (abs(left_depth - right_depth) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);

    }
private:
    int getDepth(TreeNode* root){
        if(!root) return 0;
        return max(getDepth(root->left), getDepth(root->right)) + 1;
    }
};