我正在做這個 leetcode 問題：https ://leetcode.com/problems/balanced-binary-tree/ 我已經完成了另一個使用高度函式的實作。那個有效。
我有這個其他實作。從視覺上看，當我查看問題時，我明白為什么它不起作用。但我找不到詞來為自己寫下它為什么不起作用。它在第 214 次測驗中失敗[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
}
}
需要明確的是，我不是在尋找替代解決方案。我只是想了解為什么當前的實作不起作用。
uj5u.com熱心網友回復：
以這棵樹為例：
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)
...并且這兩個遞回呼叫將回傳 true，因為確實這些子樹本身是平衡的，因此這棵樹將被識別為平衡的。但很明顯，情況并非如此。
您確實需要檢索子樹的高度并進行比較。
uj5u.com熱心網友回復：
這不是替代解決方案，我只是洗掉了不必要的檢查...
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轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/363465.html
上一篇：最不常用(LFU)快取跟蹤
下一篇：如何用代入法求解這個遞推函式？