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 ofevery node
never differ by more than 1.
判断给定的树是否是平衡的,比较简单,两个条件:左右子树都是平衡的;左右高度差值小于等于1;
判断左右子树的过程我们可以放在求高度中,把原始的求高度的递归算法改一下就好了。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function int h=0; return check(root,h); } bool check(TreeNode* root,int& h) { if ( !root ) { h=0; return true; } int lh=0,rh=0; bool ans=check(root->left,lh)&&check(root->right,rh); if (ans) { h=max(lh,rh)+1; } return ans&&(lh-rh<=1&&lh-rh>=-1); } };