如何确定二叉树是平衡的还是不使用递归

Question

如果树是平衡的，我试图返回true，如果不是平衡的，则返回false下面的递归解决方案，但我没有更正正确的布尔值。我觉得比较树的最高高度和较低高度有什么意义？不确定我错在哪里

function tree (rootNode) {
// Your code here
if (!rootNode) return 0;
if (!rootNode.left && !rootNode.right) return 0;
let minHeigth = 1 + Math.min(tree(rootNode.left), tree(rootNode.right))
let maxHeigth = 1 + Math.max(tree(rootNode.left), tree(rootNode.right))
if(maxHeigth - minHeigth <= 1){
return true
}else{
return false
}
}

Answer 1

我的递归算法是这样的。

function isBalanced(rootNode){
if(rootNode == null){
return true;
}
if(checkHeight(rootNode) === -1){ 
return false; 
} else{
return isBalanced(root.left) && isBalanced(root.right);  
}
}

将检查高度的辅助方法checkHeight将是

function checkHeight(rootNode){
if(root ==null){
return 0;
}
let leftHeight=checkHeight(root.left);
let rightHeight=checkHeight(root.right);
if(Math.abs(leftHeight - rightHeight) > 1){
return -1;
}
else{
return Math.max(leftHeight,rightHeight) +1;
}
}

注意：此算法将具有O(N(的时间复杂性

Answer 2

主要问题是您的函数混合了两件事：

• 返回高度(数字(
• 返回是否平衡(布尔值(

如果最终目的是返回布尔值，那么您需要一个不同的函数来获取高度(一个数字(。

其次，在确定高度时，代码的前两行显示不一致：

• 对于null(空(树，确定其高度为0
• 对于没有子节点的节点，还确定其高度为0

然而这两棵树的高度不同。如果单个节点(根(的高度为0，则空树的高度为-1。这与维基百科一致：

节点的高度是从该节点到叶的最长向下路径的长度。根的高度就是树的高度。节点的深度是到其根的路径的长度(即其根路径(。这在操作各种自平衡树，特别是AVL树时通常需要。根节点的深度为零，叶节点的高度为零，只有一个节点的树(因此同时有根和叶(的深度和高度为零。按照惯例，空树(如果允许的话，没有节点的树(的高度为−1。