网站制作多少钱公司网站建设详细方案模板

题目：

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 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 。

思路：

1. 采用递归的方法，检查每个节点的左右子树的高度差是否不超过1。
2. 一旦有任何一个节点不满足平衡二叉树的条件，那么整个二叉树一定不是平衡二叉树。
3. 采用类似后序遍历的方法，先检查左子树的节点，再检查右子树的节点，最后是根。
4. 递归计算，直到计算完整个树。

C代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int GetHeight(struct TreeNode* root){if(root == NULL) return 0;int LeftHeight = GetHeight(root -> left);if(LeftHeight == -1) return -1;int RightHeight = GetHeight(root -> right);if(RightHeight == -1) return -1;if(fabs(LeftHeight - RightHeight) > 1){return -1;}else{return fmax(LeftHeight, RightHeight) + 1;}
}bool isBalanced(struct TreeNode* root) {return GetHeight(root) >= 0;
}