给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3 / \ \ 9 20 20 / \ / \ 15 7 15 7二叉树A是高度平衡的二叉树，但是B不是
分析：可以利用求二叉树的深度的代码，然后利用递归或者前序、中序、后序的方法遍历每个结点，只要有一个结点不平衡，则返回false. 但是这种方法每个结点要遍历多次，时间效率不高。
每个节点只遍历一次的解法
如果我们用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录他的深度（某一结点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。
代码：
class Solution { public: /** * @param root: The root of binary tree. * @return: True if this Binary tree is Balanced, or false. */ bool isbalanced(BinaryTreeNode* root) { if(root==NULL) return true; int left=TreeDepth(root->left); int right=TreeDepth(root->right); int diff=left-right; if(diff>1||diff<-1) return false; return isbalanced(root->left)&&isbalanced(root->right); } int TreeDepth(BinaryTreeNode* root) { if(root==NULL) return 0; int nleft=TreeNode(root->left); int nroot=TreeNode(root->right); return (nleft>nright)?(nleft+1):(nright+1); } };
