網(wǎng)站制作要花多少錢(qián)百度一下百度網(wǎng)站
題目：
實(shí)現(xiàn)一個(gè)函數(shù)，檢查二叉樹(shù)是否平衡。在這個(gè)問(wèn)題中，平衡樹(shù)的定義如下：任意一個(gè)節(jié)點(diǎn)，其兩棵子樹(shù)的高度差不超過(guò) 1。
示例 1：
給定二叉樹(shù) [3,9,20,null,null,15,7]3/ \9 20/ \15 7 返回 true 。
示例 2：
給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]1/ \2 2/ \3 3/ \ 4 4 返回?false 。
思路：
- 采用遞歸的方法，檢查每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差是否不超過(guò)1。
- 一旦有任何一個(gè)節(jié)點(diǎn)不滿足平衡二叉樹(shù)的條件，那么整個(gè)二叉樹(shù)一定不是平衡二叉樹(shù)。
- 采用類似后序遍歷的方法，先檢查左子樹(shù)的節(jié)點(diǎn)，再檢查右子樹(shù)的節(jié)點(diǎn)，最后是根。
- 遞歸計(jì)算，直到計(jì)算完整個(gè)樹(shù)。
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;
}