110. Balanced Binary Tree
給定一棵二元樹，判斷它是否是高度平衡的。
範例：
輸入：root = [3,9,20,null,null,15,7] 輸出：true
這表明根據給定的二元樹，判斷它是否是高度平衡的。如果每個節點的兩個子樹的高度差不超過1，則該二元樹是高度平衡的。
Python
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def check_height(node: Optional[TreeNode]) -> int:
if not node:
return 0
left_height = check_height(node.left)
if left_height == -1:
return -1
right_height = check_height(node.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return check_height(root) != -1
17.63MB, 44ms
C++
#include <algorithm> // For std::max
using namespace std;
class Solution {
public:
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
private:
int checkHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = checkHeight(node->left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = checkHeight(node->right);
if (rightHeight == -1) {
return -1;
}
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return max(leftHeight, rightHeight) + 1;
}
};
21.45MB, 10ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
function checkHeight(node) {
if (node === null) {
return 0;
}
const leftHeight = checkHeight(node.left);
if (leftHeight === -1) {
return -1;
}
const rightHeight = checkHeight(node.right);
if (rightHeight === -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
return checkHeight(root) !== -1;
};
54.38MB, 54ms
