首页 > 代码库 > Balanced Binary Tree

Balanced Binary Tree

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.

思路:本质上是对二叉树进行遍历。IsBalancedSub( node )判断以node为根的子树是否平衡,同时返回该子树的深度。

 1 class Solution { 2 public: 3     bool isBalanced( TreeNode *root ) { 4         return IsBalancedSub( root ) != -1; 5     } 6 private: 7     int IsBalancedSub( TreeNode *node ) { 8         if( !node ) { return 0; } 9         int left = IsBalancedSub( node->left );10         if( left == -1 ) { return -1; }11         int right = IsBalancedSub( node->right );12         if( right == -1 ) { return -1; }13         if( abs( left-right ) > 1 ) { return -1; }14         return max( left, right ) + 1;15     }16 };