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 ofeverynode never differ by more than 1.
方法一：求出左右子树的深度，如果差值大于1，，则返回false，否则递归判断其左右孩子结点。但该方法每一次递归都要计算一次子结点的深度，出现重复计算。
int maxDepth(TreeNode* root){if(NULL==root)return 0;int left=maxDepth(root->left);int right=maxDepth(root->right);return 1+(left>right?left:right);}bool isBalanced(TreeNode* root){if(NULL==root)return true;int leftLength=maxDepth(root->left);int rightLength=maxDepth(root->right);int diff=leftLength-rightLength;if(diff>1 || diff<-1)return false;return isBalanced(root->left) && isBalanced(root->right);}方法二：设置一个变量，用于记录深度，不必须重复计算。
/** * 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: bool isBalanced(TreeNode* root,int *depth){if(NULL==root){*depth=0;return true;}int leftLength,rightLength;if(isBalanced(root->left,&leftLength) && isBalanced(root->right,&rightLength)){//若两棵子树都是平衡二叉树int diff=leftLength-rightLength;if(diff<=1 && diff>=-1){*depth=1+(leftLength>rightLength?leftLength:rightLength);return true;}}return false;}bool isBalanced(TreeNode* root) {int depth;return isBalanced(root,&depth);}};
为什么？答：点线杆上贴着”“此处不许小便！”
