我的tree定义类型如下
type 'a tree = Leaf of 'a | Node of 'a * 'a tree * 'a tree ;;
我有一个函数来查找树的深度如下
let rec depth = function
| Leaf x -> 0
| Node(_,left,right) -> 1 + (max (depth left) (depth right))
;;
这个函数不是尾递归的.有没有办法让我以尾递归的方式编写这个函数？
今天我接受采访时,我被要求编写一个程序,该程序采用二叉树,如果它也是二进制搜索树则返回true,否则为false.
我的方法1:执行有序遍历并将元素存储在O(n)时间内.现在扫描数组/元素列表并检查第 i 个索引处的元素是否大于第(i + 1)个索引处的元素.如果遇到这种情况,则返回false并退出循环.(这需要O(n)时间).最后回归真实.
但这位先生希望我提供一个有效的解决方案.我尝试但是我没有成功,因为要查找它是否是BST我必须检查每个节点.
而且他指着我思考递归.我的方法2:如果对于任何节点N N>左<N和N>右> N,并且N的左节点的有序后继小于N并且有序后继,则BT是BST N的右节点大于N,左右子树是BST.
但这会很复杂,而且运行时间似乎并不好.如果您知道任何最佳解决方案,请帮忙.
首先,这个问题是不是一个DUP 这一个,而是以它.
以该问题中的树为例,
1
/ \
2 3
/ / \
4 5 6
你会如何修改你的程序来打印它,
1
2 3
4 5 6
而不是一般
1
2
3
4
5
6
我基本上是以最有效的方式寻找直觉 - 我有一个方法,包括将结果附加到列表,然后循环遍历它.一种更有效的方法可能是在弹出每个级别时存储最后一个元素,然后打印出一个新行.
想法？
我们必须将二叉树的节点写入文件.什么是编写二叉树最节省空间的方法.我们可以将它存储在数组格式中,父级位于i其中,子级位于2i,2i+1.但是在稀疏二叉树的情况下,这将浪费大量空间.
如果C++ STL包含二进制搜索树(BST)实现,或者我应该构建自己的BST对象,请知道吗？
如果STL没有实施BST,是否有可用的库？
我的目标是能够尽快找到所需的记录:我有一个记录列表(它不应该是几千个.),我在该列表中执行每帧(它的计算机游戏)搜索.我使用unsigned int作为我感兴趣的记录的标识符.无论什么方式,最快的将最适合我.
我编写了以下代码来检查树是否是二进制搜索树.请帮我查一下代码:
好的!代码现在已编辑.以下帖子中有人建议使用这个简单的解决方案:
IsValidBST(root,-infinity,infinity);
bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}
我今天去接受采访,要求我序列化一棵二叉树.我实现了一种基于数组的方法,其中节点i的子节点(在水平顺序遍历中编号)处于左子节点的2*i索引和右子节点的2*i + 1.面试官似乎或多或少都很高兴,但我想知道序列化究竟意味着什么？它是否专门用于展平树以写入磁盘,或者序列化树还包括将树转换为链表,比方说.另外,我们如何将树扁平化为(双重)链表,然后重构它？您可以从链表重新创建树的确切结构吗？
今天早上,我正在阅读Steve Yegge的文章:当多态性失败时,当我遇到一个问题时,他的同事在他们来亚马逊采访时曾经问过潜在的员工.
作为多态行动的一个例子,让我们来看看经典的"eval"面试问题,据我所知,这个问题是由Ron Braunstein带到亚马逊的.这个问题非常丰富,因为它设法探究各种重要技能:OOP设计,递归,二叉树,多态和运行时输入,一般编码技巧,以及(如果你想更加努力)解析理论.
在某些时候,候选人希望你能够将算术表达式表示为二叉树,假设你只使用二进制运算符,如"+"," - ","*","/".叶节点都是数字,内部节点都是运算符.评估表达意味着走树.如果候选人没有意识到这一点,你可以轻轻地引导他们,或者如果有必要,告诉他们.
即使你告诉他们,这仍然是一个有趣的问题.
问题的前半部分,一些人(他的名字我将保护我的垂死气息,但他们的姓名首字母是威利刘易斯)感觉是工作要求,如果你想打电话给自己一个开发人员和工作在亚马逊,实际上是有点难.问题是:你如何从算术表达式(例如字符串),如"2 +(2)"到表达式树.在某些时候,我们可能会对此问题进行ADJ挑战.
下半部分是:假设这是一个2人的项目,你的合作伙伴,我们称之为"Willie",负责将字符串表达式转换为树.你可以轻松获得:你需要决定Willie用什么类构建树.您可以使用任何语言进行操作,但请确保选择一种语言,否则Willie将为您提供汇编语言.如果他感觉不舒服,那将是一个不再生产的处理器.
你会对有多少候选人感到惊讶.
我不会泄露答案,但标准不良解决方案涉及使用开关或案例陈述(或只是好老式的级联ifs).一个稍微好一点的解决方案涉及使用函数指针表,而可能最佳解决方案涉及使用多态.我鼓励你在某个时候完成它.好玩的东西!
所以,让我们尝试以三种方式解决问题.你如何使用cascaded-if,一个函数指针表和/或多态来从算术表达式(例如字符串中)如"2 +(2)"到表达式树？
随意解决一个,两个或所有三个问题.
[更新:修改标题以更好地匹配大多数答案.]
二进制搜索树对具有二分搜索的排序数组有什么好处？只是通过数学分析我没有看到差异,所以我假设低级实现开销必须存在差异.平均病例运行时间的分析如下所示.
使用二进制搜索
搜索的排序数组:O(log(n))
插入:O(log(n))(我们运行二进制搜索以查找插入元素的位置)
删除:O(log(n))(我们运行二进制搜索找到要删除的元素)
二进制搜索树
搜索:O(log(n))
插入:O(log(n))
删除:O(log(n))
对于上面列出的操作,二进制搜索树具有最坏的O(n)情况(如果树不平衡),所以这看起来实际上比使用二进制搜索的排序数组更差.
另外,我不假设我们必须预先对数组进行排序(这将花费O(nlog(n)),我们将逐个插入元素到数组中,就像我们对二叉树所做的那样.唯一的好处BST我可以看到它支持其他类型的遍历,如inorder,preorder,postorder.
arrays algorithm binary-tree time-complexity data-structures
以下是面试问题.
您将获得一个二叉树(不一定是BST),其中每个节点都包含一个值.设计一种算法来打印总计到该值的所有路径.请注意,它可以是树中的任何路径 - 它不必从根开始.
虽然我能够在树中找到从根开始的所有路径都有给定的总和,但是我无法对从不在根处开始的路径这样做.