难度:Easy
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]1/ \2 2/ \3 3/ \4 4返回 false 。
通过树的高度判断。
/*** 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 {private:int deep(TreeNode* root){if(!root) return 0;int r=1,l=1;if(!root->left && !root->right) return 1;if(root->left) l+=deep(root->left);if(root->right) r+=deep(root->right);if(l<0 || r<0 || abs(l-r) > 1) return INT_MIN;return max(l,r);}public:bool isBalanced(TreeNode* root) {if(!root) return true;// cout<<deep(root)<<endl;return deep(root)>0;}};
执行用时 :32ms, 在所有 C++ 提交中击败了39.18%的用户 内存消耗 :17.4MB, 在所有 C++ 提交中击败了21.21%的用户