有人可以帮我理解下面的Morris inorder树遍历算法而不使用堆栈或递归吗？我试图了解它是如何工作的,但它只是逃避了我.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a. Print current’s data
b. Go to the right, i.e., current = current->right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current->left
我理解的树被修改的方式,将current node在作出right child的的max node中right subtree和使用该财产序遍历.但除此之外,我迷失了.
编辑:找到这个附带的c ++代码.我很难理解修改后树的恢复方式.神奇在于else子句,一旦修改了正确的叶子就会被击中.请参阅代码了解详情:
/* Function to traverse binary …我最喜欢的面试问题之一是
在O(n)时间和O(1)空间中,确定链表是否包含循环.
这可以使用Floyd的循环寻找算法来完成.
我的问题是,在尝试检测二叉树是否包含循环时,是否可以获得如此好的时间和空间保证.也就是说,如果有人给你一个struct定义
struct node {
node* left;
node* right;
};
您如何有效地验证给定结构确实是二叉树,而不是DAG或包含循环的图形？
是否存在一种算法,给定二叉树的根,可以确定该树是否包含O(n)时间并且优于O(n)空间的循环？显然,这可以使用标准DFS或BFS来完成,但这需要O(n)空间.可以在O(√n)空间内完成吗？O(log n)空间？或者(O圣)在O(1)空间？我很好奇,因为在链表的情况下,这可以在O(1)空间中完成,但我从未见过相应有效的算法.
可能重复:
是否存在无法使用尾递归写入的问题？
根据我的理解,尾递归是一种优化,当递归调用不需要来自它将发送垃圾邮件的递归调用的信息时,您可以使用它.
那么可以使用尾递归实现所有递归函数吗？像DFS这样的东西,你需要最内层的孩子在父母可以之前返回？
给定一个带有整数,左右指针的二叉树,如何在O(n)时间和O(1)额外内存(没有堆栈/队列/递归)中遍历树？
这个人给出了一个解决方案,该解决方案不是将当前路径编码为整数的O(n)总时间(因此适用于有限深度的树).
我正在寻找经典的解决方案
(SPOILER)
编码子节点中每个节点的父节点.
我有一个AVL树.每个节点如下所示:
typedef struct {
Node *parent; // the parent node
Node *left; // the node left of this node
Node *right; // the node right of this node
int height; // the height of this node
void *value; // payload
} Node;
是否可以在O(1)空间中使用这些节点迭代AVL树,而不进行递归,如果是,如何？
如果不是,那么也可以理解具有sub-O(n)空间或iff真正必要的O(N)空间的解决方案.
迭代树我的意思是我想要访问每个节点一次,如果可能的话,按顺序(从最左边到mostright节点).
我在 pascal （或 delphi ）中编写了一个递归树函数，但是当我运行它时，我收到了“内存不足”消息。我需要将这段代码中的计算递归函数转换为非递归函数，你能告诉我怎么做吗：
program testing(input, output);
type
ptr = ^tr;
tr = record
age: byte;
left, right: ptr;
end;
var
topper: ptr;
total, day: longint;
procedure mycreate(var t: ptr);
var
temp:ptr;
begin
new(temp);
temp^.age := 1;
temp^.left := nil;
temp^.right := nil;
t := temp;
end;
procedure gooneday(var t: ptr);
begin
if t^.age <> 5 then
begin
if t^.age = 2 then
mycreate(t^.left)
else if t^.age = 3 then
mycreate(t^.right);
t^.age := t^.age + 1;
total := total …