在一次采访中询问了这个问题:给定两个未排序的数组,检查它是否会创建相同的bst.例如:2,1,4,0和2,1,0,4都将形成相同的BST.
2
/ \
1 4
/
0
请建议一些好的算法.
哪个会花更长的时间？
按排序顺序打印存储在二叉查找树中的所有项目,或按排序顺序打印存储在哈希表中的所有项目.
由于哈希表从未排序正确,因此以排序顺序打印哈希表的项目需要更长的时间？和BST是？
如果我插入项目:10,12,14,1,6到二进制最小堆一个项目接一个怎么样的结果,我的问题是以下
当我开始时我有:
10
然后
10
/
12
然后
10
/ \
12 14
然后
1
/ \
10 14
/
12
但这不对,那么正确的方法是什么？
注意:这是一个功课问题,我试图理解这个概念,如果你觉得不能解决问题(这不是完整的问题)请提供一个类似问题的例子.
我正在寻找一种算法,它可以在二叉树中找到两个最远的元素,而不是寻找任何特殊语言,仅用于算法.
谢谢.
我想要计算叶子节点的数量:注意:不能使用全局/类级别变量我跟随算法,它工作正常.但我希望方法签名是
countLeaves(Node node)
我知道我可以重载methds并从1个args调用2 args方法sig,但是不想这样做.任何人都可以建议任何其他方法吗？
int countLeaves(Node node,int count){
if(node==null)
return 0;
if(node.left==null && node.right==null){
return 1+count;
}else{
int lc = countLeaves(node.left, count);
int total = countLeaves(node.right, lc);
return total;
}
}
找到二叉树的宽度.
在我的每个假期的代码中,我在哈希映射中创建一个条目,并在我离开i时找到一个节点时不断更新它.最后我将迭代hashmap以找到最大宽度.但是我怎么能不使用任何classleel/global varaiables？
Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
void width(Node node,int level){
if(node==null)
return;
if(mp.containsKey(level)){
int count = mp.get(level);
mp.put(level, count+1);
}else{
mp.put(level, 1);
}
width(node.left, level+1);
width(node.right, level+1);
}
我很难进行树遍历,因此就像瘟疫一样避免它...通常.
我有一个类(这里略微简化版本,但在功能上相同),如:
class Branch(object):
def __init__(self, title, parent=None):
self.title = title
self.parent = parent
我有一堆Branch实例的字典,每个实例的标题作为键:
tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar}
现在,我知道有一些复杂的算法可以实现遍历效率(例如MPTT等),尤其适用于效率最重要的数据库驱动项目.我根本不使用数据库,只使用简单的内存中对象.
考虑到titlea Branch,我需要得到list该分支的所有后代(儿童,孩子的孩子,等等)tree,所以:
注意:这不是家庭作业.我不在学校.算法真的很糟糕.我已经将Django MPTT用于需要DB存储树的项目......但仍然不太了解它.
有人可以建议我什么时候需要Level-Order Traversal(解决一些实际/现实生活场景)？
我编写了foldTree从列表构建平衡二叉树的函数.我必须使用foldr,它没关系,我使用它,但我使insertInTree函数递归=(现在我只知道这种方式穿过树=)).
更新:我不确定功能insertTree:是否正确计算递归的高度？=((这里需要一些帮助.
是否可以在insertInTree没有递归的情况下编写(使用某些东西until/iterate/unfoldr)或者在foldTree没有辅助函数的情况下编写函数=>以某种方式缩短？
这是我的尝试如下:
data Tree a = Leaf
| Node Integer (Tree a) a (Tree a)
deriving (Show, Eq)
foldTree :: [a] -> Tree a
foldTree = foldr (\x tree -> insertInTree x tree) Leaf
insertInTree :: a -> Tree a -> Tree a
insertInTree x Leaf = Node 0 (Leaf) x (Leaf)
insertInTree x (Node n t1 val t2) = if h1 < …我知道有很多关于定义二叉树以检查某些东西是否是二叉树的问题,但我找不到一个在"相反的方向"处理这个问题的线程.
为什么二进制树的定义在被称为"es_arbol(X)"时不会返回所有可能的二叉树？详细解释并尝试实现一个返回所有可能的二叉树结构的不同定义.
好吧,所以基本上我被困在一个任务的这一部分.在定义我的二叉树验证函数后,我注意到当没有参数调用它只返回通过它们的右节点"增长"的树,或者至少是如何我解释swi-prolog的输出.我没有得到的是,假设我的定义是正确的,Prolog应该能够以两种方式构建它们.如果没有,我想如果有人能指出我正确的工作方向找出二叉树的更一般的定义,或者解释为什么我的定义不够.
这是我的定义:
es_arbol(nil).
es_arbol(arbol(_,I,D)) :- es_arbol(I), es_arbol(D).