输入一棵二叉树，判断该二叉树是否是平衡二叉树。

分析：

平衡二叉树定义

递归解法 AC代码：

#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;

}

LeetCode 110. Balanced Binary Tree

Total Accepted: 111269 Total Submissions: 326144 Difficulty: Easy

提交网址: https://leetcode.com/problems/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.

AC代码：

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)); // 继续递归判断

    }

};