55 - II. 平衡二叉樹
Ideas
這題直接扣平衡二叉樹的定義就可以了，需要寫一個輔助函式用來計算二叉樹的高度，然后計算根節點左右子樹的高度差，滿足深度相差不超過1，那么它就是一棵平衡二叉樹，
Code
C++
class Solution {
public:
int get_height(TreeNode* node) {
if (node == NULL) {
return 0;
} else {
return max(get_height(node->left), get_height(node->right)) + 1;
}
}
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
}
int left_height = get_height(root->left);
int right_height = get_height(root->right);
return abs(left_height - right_height) < 2 && isBalanced(root->left) && isBalanced(root->right) ? true : false;
}
};
極限壓縮版：
class Solution {
public:
int get_height(TreeNode* node) {
return node == NULL ? 0 : max(get_height(node->left), get_height(node->right)) + 1;
}
bool isBalanced(TreeNode* root) {
return root == NULL ? true : abs(get_height(root->left) - get_height(root->right)) < 2 && isBalanced(root->left) && isBalanced(root->right) ? true : false;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/386801.html
標籤：其他
上一篇：大聰明教你學Java | Log4j 漏洞到底是怎么一回事？Log4j 2.15.0 也不靠譜了...
下一篇：周總結（12.13-12.19）