Open Tcdian opened 3 years ago
/**
* 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) {
let maxDifference = 0;
calcDepth(root);
return maxDifference <= 1;
function calcDepth(root) {
if (maxDifference > 1) {
return maxDifference;
}
if (root === null) {
return 0;
}
const leftDepth = calcDepth(root.left);
const rightDepth = calcDepth(root.right);
maxDifference = Math.max(maxDifference, Math.abs(leftDepth - rightDepth));
return Math.max(leftDepth, rightDepth) + 1;
}
};
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isBalanced(root: TreeNode | null): boolean {
let maxDifference = 0;
calcDepth(root);
return maxDifference <= 1;
function calcDepth(root: TreeNode | null): number {
if (maxDifference > 1) {
return maxDifference;
}
if (root === null) {
return 0;
}
const leftDepth = calcDepth(root.left);
const rightDepth = calcDepth(root.right);
maxDifference = Math.max(maxDifference, Math.abs(leftDepth - rightDepth));
return Math.max(leftDepth, rightDepth) + 1;
}
};
110. Balanced Binary Tree
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
Example 1
Given the following tree
[3,9,20,null,null,15,7]
Return true.
Example 2
Given the following tree
[1,2,2,3,3,null,null,4,4]
Return false.