我正在进行一个使用二进制搜索树的项目。这个项目要求我创建一个名为isBalanced的方法,检查二进制搜索树是否在容差范围内平衡。我想办法做到这一点,但速度慢得可怕。我想知道是否有人有什么技巧可以提高它的效率。顺便说一句,如果子项为null,.getLeftChild()和.getRightChild(。我更希望他们亲自返回null。
以下是我的代码片段:
@Override
public <T> int getDepth(BinaryTreeNode<T> root) {
return recDepth(root,0);
}
public <T> int recDepth(BinaryTreeNode<T> root,int depth) {
int leftTree,rightTree;
if(!root.hasLeftChild()&&!root.hasRightChild()) return depth;
if(!root.hasLeftChild()) leftTree = 0;
else leftTree = recDepth(root.getLeftChild(),depth+1);
if(!root.hasRightChild()) rightTree = 0;
else rightTree = recDepth(root.getRightChild(),depth+1);
if(rightTree>leftTree) return rightTree;
else return leftTree;
}
@Override
public <T> boolean isBalanced(BinaryTreeNode<T> root, int tolerance) {
if(tolerance<0) throw new IllegalArgumentException("Can't have negative tolerance");
if(root==null) throw new NullPointerException();
return recBalanced(root,tolerance);
}
public <T> boolean recBalanced(BinaryTreeNode<T> root, int tolerance){
try{
if(Math.abs(getDepth(root.getLeftChild())-getDepth(root.getLeftChild()))<=tolerance){
return recBalanced(root.getLeftChild(),tolerance)&&recBalanced(root.getRightChild(),tolerance);
}else return false;
} catch (IllegalStateException e){
if(root.hasLeftChild()&&getDepth(root.getLeftChild())>tolerance-1) return false;
else if(root.hasRightChild()&&getDepth(root.getRightChild())>tolerance-1) return false;
else return true;
}
}
提前感谢您的帮助。
您的效率问题来自于这样一个事实,即您要多次遍历相同的元素来计算子树的深度,然后计算其左右子树的深度。
当你有这样的重叠问题,可以通过较小的问题推导出来时,你的脑海中一定会响起一个铃声:动态编程。您可以计算一个BinaryTreeNode<Integer>
,它将包含每个相应节点的深度(该树的形状与原始树相同)。然后,您只需要遍历该树一次就可以执行计算,总时间复杂度为O(n)
(然而,O(n)
使用的内存)。
public BinaryTreeNode<Integer> computeDepthTree(BinaryTreeNode<T> bt) {
return computeDepth(bt,0);
}
public BinaryTreeNode<Integer> computeDepthTree(BinaryTreeNode<T> bt, int depth) {
BinaryTreeNode<Integer> result = new BinaryTreeNode<>(depth);
if (bt.getLeftNode() != null)
result.setLeftNode(computeDepthTree(bt.getLeftNode(),depth + 1));
if (bt.getRightNode() != null)
result.setRightNode(computeDepthTree(bt.getRightNode(),depth + 1));
return result;
}
通过计算该树,当遍历给定节点时,您将在O(1)
中访问其深度,因此比较同一父节点的子节点之间的深度将非常便宜!