这段代码应该改变什么才能正确识别平衡树？

Question

我正在做 this leetcode problem。我已经完成了另一个使用高度函数的实现。行得通。

我有另一个实现。从视觉上看问题时，我明白为什么它不起作用。但我找不到文字来为自己写下它为什么不起作用。它在 [1, 2, 2, 3, 3, null, null, 4, 4]

的第 214 次测试中失败

class Solution {
    // for every node I have to go 2 levels down. 
    // if left existed, then see if right exists, and traverse down 
    // if left existed and had children but right didn't exist then return `false`
    // or if right existed and had children but left didn't exist then return `false`
    func isBalanced(_ root: TreeNode?) -> Bool {
        if let left = root?.left {
            if let right = root?.right {
                return isBalanced(left) && isBalanced(right)
            } else if left.left != nil || left.right != nil {
                    return false
                }
        } else if let right = root?.right {
            if root?.left == nil {
                if right.left != nil || right.right != nil {
                    return false
                }
            }
        }
        return true
    }
}

明确地说，我不是在寻找替代解决方案。我只是想了解为什么当前的实现不起作用。

Answer 1

这不是替代解决方案，我只是删除了不必要的检查...

class TreeNode {
    constructor(left, right) {
        this.left = left
        this.right = right
    }
    isEndNode() { return this.left == null && this.right == null; }
    isBalanced() {
        if (this.isEndNode()) return true;

        if (this.left && this.right)
            return this.left.isBalanced() && this.right.isBalanced();

        return false
    }
}
let node = (left, right) => new TreeNode(left, right);

let root1 = node(node(node(), node()), node(node(), node()))
let root2 = node(node(node(), node()), node(node(), null))
let root3 = node(node(null, node()), node(node(), node()))

console.log(root1.isBalanced()) // true
console.log(root2.isBalanced()) // false
console.log(root3.isBalanced()) // false

Answer 2

以这棵树为例：

                  8
                /   \
               4     9
             /   \
            2     6
           / \   / \
          1   3 5   7

从根开始，这段代码的执行会进入内部if块：

    if let left = root?.left {
        if let right = root?.right {
            return isBalanced(left) && isBalanced(right)

...并且这两个递归调用将 return 为真，因为这些子树本身确实是平衡的，因此这棵树将被识别为平衡的。但很明显，情况并非如此。

您确实需要检索子树的高度并进行比较。

这段代码应该改变什么才能正确识别平衡树？

What should change for the this code to correctly identify balanced Trees?

algorithm

tree

binary-tree

swift