68:Balanced Binary Tree


題目:Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two

subtrees of every node never differ by more than 1.


該題目應選擇遞歸解法,但遞歸解法有兩種版本,第二種版本要比第一種版本更好


遞歸版本一


// 迭代版本一
// 該版本缺點就是節點高度值會重復計算
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root) return true;

int diff = abs(height(root -> left) - height(root -> right))
if (diff <= 1) return isBalanced(root -> left) && isBalanced(root -> right);
else return false;
}
private:
int height(TreeNode* root) {
if (!root) return 0;

int h = max(height(p -> left), height(p -> right)) + 1;
return h;
}
};

遞歸版本二:


// 迭代版本 二
// 時間復雜度 O(n),空間復雜度 O(log n)
class Solution {
public:
bool isBalanced(TreeNode* root) {
return balancedHeight(root) >= 0;
}

int balancedHeight(TreeNode* root) {
if (!root) return 0;

int left = balancedHeight(root -> left);
int right = balancedHeight(root -> right);

if (left < 0 || right < 0 || abs(left - right) > 1) return -1; // 剪枝

return max(left, right) + 1;
}
};

0 個評論

要回覆文章請先登錄註冊