C++版 - 剑指offer 面试题39：判断平衡二叉树(LeetCode 110. Balanced Binary Tree) 题解

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{
    int val; 
    TreeNode *left; 
    TreeNode *right; 
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
}; 
class Solution {
public:
	int getHeight(TreeNode *root)
	{
		if(root==NULL) return 0;
		int lh=getHeight(root->left);
		int rh=getHeight(root->right);
		int height=(lh<rh)?(rh+1):(lh+1);  // 记住：要加上根节点那一层，高度+1 
		return height;
	}
    bool IsBalanced_Solution(TreeNode* pRoot) {
		if(pRoot==NULL) return true;
		int lh=getHeight(pRoot->left);
		int rh=getHeight(pRoot->right);
		if(lh-rh>1 || lh-rh<-1)	return false;
		else return (IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right)); // 继续递归判断	
    }
};
// 以下为测试 
int main()
{
	Solution sol;      
    TreeNode *root = new TreeNode(1);  
    root->right = new TreeNode(2);  
    root->right->left = new TreeNode(3);      
    bool res=sol.IsBalanced_Solution(root); 
    cout<<res<<" ";
    return 0; 
}

class Solution {
public:
	int getHeight(TreeNode *root)
	{
		if(root==NULL) return 0;
		int lh=getHeight(root->left);
		int rh=getHeight(root->right);
		int height=(lh<rh)?(rh+1):(lh+1);  // 记住：要加上根节点那一层，高度+1 
		return height;
	}
    bool isBalanced(TreeNode *root) {
		if(root==NULL) return true;
		int lh=getHeight(root->left);
		int rh=getHeight(root->right);
		if(lh-rh>1 || lh-rh<-1)	return false;
		else return (isBalanced(root->left) && isBalanced(root->right)); // 继续递归判断	
    }
};