網(wǎng)站制作要花多少錢百度一下百度網(wǎng)站
題目：
實現(xiàn)一個函數(shù)，檢查二叉樹是否平衡。在這個問題中，平衡樹的定義如下：任意一個節(jié)點，其兩棵子樹的高度差不超過 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 。
思路：
- 采用遞歸的方法，檢查每個節(jié)點的左右子樹的高度差是否不超過1。
- 一旦有任何一個節(jié)點不滿足平衡二叉樹的條件，那么整個二叉樹一定不是平衡二叉樹。
- 采用類似后序遍歷的方法，先檢查左子樹的節(jié)點，再檢查右子樹的節(jié)點，最后是根。
- 遞歸計算，直到計算完整個樹。
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;
}