I’m doing this leetcode problem: https://leetcode.com/problems/balanced-binary-tree/ I already have done another implementation that uses a height function. That works.
I have this other implementation. Visually when I look at the problem I get why it won’t work. But I can’t find words to write it down for myself as to why it doesn’t work.
It fails on its 214th test for [1,2,2,3,3,null,null,4,4]
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
}
}
To be clear I'm not looking for alternate solutions. I'm only trying to understand why the current implementation doesn't work.
CodePudding user response：
Take for instance this tree:
8
/ \
4 9
/ \
2 6
/ \ / \
1 3 5 7
Starting at the root, the execution of this code will enter the inner if block:
if let left = root?.left {
if let right = root?.right {
return isBalanced(left) && isBalanced(right)
...and the two recursive calls will return true, because indeed those subtrees are balanced on their own, and so this tree will be identified as balanced. Yet it is clear this is not the case.
You will really need to retrieve the heights of the subtrees and compare them.
CodePudding user response：
This isn't an alternate solutions, I just removed unnecessary check...
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