110、平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
链接：https://leetcode-cn.com/problems/balanced-binary-tree
递归+二叉树的高度

#include "pch.h"
#include <windows.h>
#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:
	bool isBalanced(TreeNode* root) {
		return CheckBalance(root) >= 0;
	}

	int CheckBalance(TreeNode* root) {
		if (root == NULL)
		{
			return 0;
		}
		int Lh = CheckBalance(root->left);
		if ( Lh < 0 )
		{
			return Lh;
		}
		int Rh = CheckBalance(root->right);
		if ( Rh < 0 )
		{
			return Rh;
		}
		if (abs(Lh - Rh) < 2)
		{
			return max(Lh, Rh) + 1;
		}
		return -1;
	}
};

TreeNode* ConstructBinaryTree(int *arr, int len, int i) {
	if (arr[i]=='#') return NULL;
	TreeNode *root = new TreeNode(arr[i]);
	int Lnode = 2 * i + 1;
	int Rnode = 2 * i + 2;
	if (Lnode > len - 1)
	{
		root->left = NULL;
	}
	if (Rnode > len - 1)
	{
		root->right = NULL;
	}
	return root;
}

int main()
{
	int data[] = { 1, 2, 3, 4, 5, '#', 6, '#', '#', 7, 8 };
	TreeNode *root = ConstructBinaryTree(data, 11, 0);
	Solution s;
	cout<<s.isBalanced(root);
}