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:
    Given the following tree [3,9,20,null,null,15,7]:
    3
    / \
    9 20
    / \
    15 7
    Return true.

    Example 2:
    Given the following tree [1,2,2,3,3,null,null,4,4]:
    1
    / \
    2 2
    / \
    3 3
    / \
    4 4
    Return false.

    Runtime: 16 ms, faster than 56.86% of C++ online submissions for Balanced Binary Tree.
    Memory Usage: 16.5 MB, less than 100.00% of C++ online submissions for Balanced Binary Tree.

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8.  * };
    9.  */
    10. class Solution {
    11. public:
    12.     bool isBalanced(TreeNode* root) {
    13.         int height = 0;
    14.         return check(root, height);
    15.     }
    18.     bool check(TreeNode *root, int& height) {
    19.         if (root == NULL) {
    20.             height = 0;
    21.             return true;
    22.         }
    23.         int leftHeight = 0;
    24.         int rightHeight = 0;
    25.         if (!check(root->left, leftHeight)) {
    26.             return false;
    27.         }
    28.         if (!check(root->right, rightHeight)) {
    29.             return false;
    30.         }
    31.         if (abs(leftHeight - rightHeight) > 1) {
    32.             return false;
    33.         }
    34.         height = max(leftHeight, rightHeight) + 1;
    35.         return true;
    36.     }
    37. };

    Runtime: 88 ms, faster than 85.22% of JavaScript online submissions for Balanced Binary Tree.
    Memory Usage: 43.2 MB, less than 41.05% of JavaScript online submissions for Balanced Binary Tree.

    1. /**
    2.  * Definition for a binary tree node.
    3.  * function TreeNode(val, left, right) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.left = (left===undefined ? null : left)
    6.  *     this.right = (right===undefined ? null : right)
    7.  * }
    8.  */
    9. /**
    10.  * @param {TreeNode} root
    11.  * @return {boolean}
    12.  */
    13. var isBalanced = function(root) {
    15.     function getDepth(node) {
    16.         if (!node) {
    17.             return 0;
    18.         }
    19.         const left = getDepth(node.left);
    20.         if (left === -1) {
    21.             return -1;
    22.         }
    23.         const right = getDepth(node.right);
    24.         if (right === -1) {
    25.             return -1;
    26.         }
    27.         const dis = Math.abs(left - right);
    28.         return dis <= 1 ? Math.max(left, right) + 1 : -1;
    29.     }
    31.     return getDepth(root) !== -1; 
    32. };