我知道我可以只看一些例子，但我花了很長時間試圖自己做到這一點，我想知道我是否成功。它通過了我給它的測驗，但是我可以對代碼進行完整性檢查嗎？
每個節點都是一個 javascript 類，其左右屬性等于另一個節點或未定義。我還為 Node 類撰寫了一個 .hasChildren() 方法，它聽起來像。
這個函式是我的 BinaryTree 類的一個方法，它有另一個方法.height()，它接受任何節點并確定從該節點開始的樹的高度。這是.isBalanced()方法，它也需要一個節點開始：
BinaryTree.prototype.isBalanced = function (node = this.root) {
const rBalanced = (node) => {
// a node with no children is balanced
if (!node.hasChildren()) {
return true
}
// get the difference in heights between the branches, using -1 for a missing child
const left = node.left ? this.height(node.left) : -1
const right = node.right ? this.height(node.right) : -1
// if the difference is 1 or less, this node is balanced
const balanced = Math.abs(left - right) <= 1
// ensure that every child tree, if it exists, is also balanced
if (node.left && !node.right) {
return balanced && rBalanced(node.left)
}
if (!node.left && node.right) {
return balanced && rBalanced(node.right)
}
return balanced && rBalanced(node.left) && rBalanced(node.right)
}
// a nonexistent tree is balanced (???)
return node ? rBalanced(node) : true
}
這是.height()以防萬一的方法：
BinaryTree.prototype.height = function (node = this.root) {
const rHeight = (node, count) => {
return Math.max(
count,
node.left ? rHeight(node.left, count 1) : null,
node.right ? rHeight(node.right, count 1) : null
)
}
return node ? rHeight(node, 1) : 0
}
編輯：這是一個帶有作業代碼的 jsfiddle https://jsfiddle.net/jonahsaltzman/u2jrosLm/
uj5u.com熱心網友回復：
函式isBalanced是正確的，但是函式存在不一致height，isBalanced導致回傳錯誤的結果。例如，對于這棵樹，它回傳false，但true應該是：
2
/
1
問題height在于它在沒有節點時回傳 0。但是在isBalanced這種情況下，您使用 -1 。比較從每個函式中提取的這兩個運算式：
node ? rHeight(node, 1) : 0
和：
node.left ? this.height(node.left) : -1
這并不一致。不存在的節點的高度為 -1 或高度為 0，但在這里您將兩者混合在一起。由于規范是將空樹視為高度 -1，因此更改以下代碼height：
node ? rHeight(node, 0) : -1
// ^^ ^^
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422793.html
標籤：
上一篇：在不使用串列的情況下顯示專案串列
下一篇：加起來等于給定自然數的組合