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 depth of the two subtrees of every node never differ by more than 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int height(TreeNode *root){ if(root == NULL){ return 0; } int leftHeight = height(root->left); if(leftHeight == -1){ return -1; } int rightHeight = height(root->right); if(rightHeight == -1){ return -1; } if(abs(leftHeight - rightHeight) > 1){ return -1; } return 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { if(root == NULL){ return true; } if(height(root) == -1){ return false; } return true; } }; |
