Problem: 110. 平衡二叉树

作者:江月迟迟

发表于:2024-12-10

字数统计:315 字

预计阅读2分钟

[TOC]

思路

带当前深度carry和不带当前深度的方法，最后发现使用标识符传递不是平衡树的信息，如果一定要用true和false来传递信息的话，那么carry有用，否则carry没用

Code

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    return getNodeDepth(root, 0) !== -1
};

const getNodeDepth = function(node, carry) {
    // 判空
    if (node === null) {
        return carry
    } else {
        carry++
    }
    const leftDepth = getNodeDepth(node.left, carry)
    const rightDepth = getNodeDepth(node.right, carry)

    if (leftDepth === -1 || rightDepth === -1 || Math.abs(leftDepth - rightDepth) > 1) {
        return -1
    }

    return Math.max(leftDepth, rightDepth)
}


const getNodeDepth = function(node) {
    // 判空
    if (node === null) {
        return 0
    }
    const leftDepth = getNodeDepth(node.left)
    const rightDepth = getNodeDepth(node.right)

    if (leftDepth === -1 || rightDepth === -1 || Math.abs(leftDepth - rightDepth) > 1) {
        return -1
    }

    return Math.max(leftDepth, rightDepth) + 1
}




var isBalanced = function(root) {
    return typeof getNodeDepth(root, 0) === 'number'
};

const getNodeDepth = function(node, carry) {
    // 判空
    if (node === null) {
        return carry
    } else {
        carry++
    }
    const leftDepth = getNodeDepth(node.left, carry)
    const rightDepth = getNodeDepth(node.right, carry)

    if (leftDepth === false || rightDepth === false || Math.abs(leftDepth - rightDepth) > 1) {
        return false
    }

    return Math.max(leftDepth, rightDepth)
}