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.

//两次递归效率不高 合并看leetcode代码

/** * 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) {        if(root==NULL) return true;        int leftDepth=getDepth(root->left);        int rightDepth=getDepth(root->right);        if(abs(leftDepth-rightDepth)>1)             return false;        else            return isBalanced(root->left)&&isBalanced(root->right);            }     //得到树的高度    int getDepth(TreeNode *node)    {        if(node==NULL)            return 0;        int leftDepth=getDepth(node->left);        int rightDepth=getDepth(node->right);        return 1+max(leftDepth,rightDepth);    }};

 

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isBalanced(TreeNode* root) {13         return balancedHeight(root)>=0;14         15     }16     17     //return the height of root if the tree is a balanced tree;18     //otherwise,return -119     int balancedHeight(TreeNode *root)20     {21         if(root==NULL) return 0;22         int left=balancedHeight(root->left);23         int right=balancedHeight(root->right);24         if(left<0||right<0||abs(left-right)>1)25             return -1;26         else27             return max(left,right)+1;28     }29 };