Best O(N) Solution
Approach 1\nBrute-Force\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Code\n\n/**\n * Definition for a binary tree node.\n * str
# Approach 1\nBrute-Force\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool isBalanced(TreeNode* root) {\n        if (root == NULL)\n            return true;\n        int lh = height(root->left); \n        int rh = height(root->right);    \n        if (abs(lh - rh) > 1)\n            return false; \n        bool left = isBalanced(root->left); \n        bool right = isBalanced(root->right);  \n        if (left == false || right == false) \n            return false;    \n        return true;\n    }\n    int height(TreeNode* root) {\n        if (root == NULL)\n            return 0;\n        int lh = height(root->left);\n        int rh = height(root->right);\n        return 1 + max (lh, rh);      \n    }\n};\n```\n\n# Approach 2\nOptimal \n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool isBalanced(TreeNode* root) {\n        if (root == NULL)\n            return true;\n        if (height(root) == -1)\n            return false;\n        return true;\n    }\n    int height(TreeNode* root) {\n        if (root == NULL)\n            return 0;\n        int lh = height(root->left);\n        if (lh == -1)\n            return -1;\n        int rh = height(root->right);\n        if (rh == -1)\n            return -1;\n        if (abs(lh - rh) > 1)\n            return -1;   \n        return 1 + max (lh, rh);    \n    }\n};\n```
['C++']