几天前,我在学习泛型树时,遇到了一个通用树直径的代码,如下所示:
static int diameter = Integer.MIN_VALUE;
public static int findDia(Node node){
int dch = -1; // dch = deepest child height
int sdch =-1; // sdch = second deepest child height
for(Node child : node.children){ // children of current node are in an arraylist , every node has data + reference of arraylist of its children
int ch = findDia(child); // ch = child height
if(ch>dch){
sdch=dch;
dch=ch;
}else if(ch>sdch){
sdch=ch;
}
}
if(sdch+dch+2>diameter){
diameter = sdch+dch+2;
}
return dch+1;
}
今天我在研究二叉树的时候,我遇到了一个类似的问题,即在二叉树中求直径,但是对于二叉树直径问题给出的解决方案与这个方法不同,有没有办法调整这个代码使它也适用于二叉树?我一直在尝试调整它,使之适用于二叉树,但每次我的代码失败一些测试用例。我没有把我的二叉树代码放在这里,因为我已经编写了多种方法,但是它们都失败了。
1条答案
按热度按时间wwtsj6pe1#
二叉树是通用树的专用版本[1],因此任何适用于通用树的只读算法也适用于二叉树。
由于查找直径是一个只读操作,因此该算法的工作原理应该基本不变。
唯一的区别是,一般树有一个子树列表,而二叉树只有两个单独的子引用,但这是代码应该很容易适应的一个小细节。
例如,你可以增强二叉树
Node
使用方法初始化以使其看起来像常规树节点:现在替换
node.children
与node.getChildren()
在代码里你就完了。参考文献1:一般树和二叉树的区别