l***c
发帖数: 55 | 1 国内的M家
题目是二叉树后续遍历，不用递归和栈，只有个parent指针。
我一直想问他他能写出来不 |
g****o
发帖数: 547 | |
u*****o
发帖数: 1224 | |
a********m
发帖数: 15480 | 4 为啥恶心？
【在 l***c 的大作中提到】
: 国内的M家
: 题目是二叉树后续遍历，不用递归和栈，只有个parent指针。
: 我一直想问他他能写出来不
|
k*******2
发帖数: 84 | 5 不是morris 给了parent指针
不过如果什么提示都不给 直接甩这道题确实还是有一定难度的 我今天也面这道提了
不过面试官给了提示 |
g****o
发帖数: 547 | 6 啥提示？
看来要把给parent指针的三种遍历练习一遍
【在 k*******2 的大作中提到】
: 不是morris 给了parent指针
: 不过如果什么提示都不给 直接甩这道题确实还是有一定难度的 我今天也面这道提了
: 不过面试官给了提示
|
l***c
发帖数: 55 | 7 我当时思路不清晰
面试完了细细想想，主要有几点：
1.找到最左边的叶子节点（rightChild == NULL), visit
2.回溯到上一个节点，如果它有右孩子，则进到右子树
如果没有，visit该节点，再回溯，直到有右子数
3. 重复到1
但如何区别从左子节点向上回溯和右子节点向上回溯？
可以currentNode->parent->rightChild == currentNode判断就
如果从右子节点回溯，则visit这个parent，否则进入右子数
当时这里没想通。
恶心的地方还在于写代码：
if判断，还要判断是否回溯到root ，还有几种特殊情况要处理，比如该节点没有左孩
子，只有右子数，或者没有右子树，只有一串只有左孩子的孩子们。。
第一次面试比较紧张，脑袋就是打转的。 |
l***c
发帖数: 55 | 8 大牛们可以试试写写代码
我下来后，思路稍微清晰，写起来还是很想骂 |
f*******w
发帖数: 1243 | |
s***e
发帖数: 403 | 10 没有什么太大的难度啊
设置两个变量，back_left, back_right，然后先向左移动。在向parent移动的时候识
别是从左边子树移动来的还是从右边子树移动来的。如果是从右边子树移动来的说明所
有右边子树已经访问过，所以就向上移动，否则访问右边子树。最后从右边移动到root
的时候表明访问完毕。需要考察的也就是根节点的右子树是否访问完全。
下面是代码，可能有bug，不过思路大致如此。
struct TreeNode
{
TreeNode* parent;
TreeNode* left;
TreeNode* right;
int value;
explicit TreeNode(int val, TreeNode* p=nullptr) :
parent(p), left(nullptr), right(nullptr), value(val)
{}
};
void traverse(TreeNode* node)
{
TreeNode* iter=node;
bool backleft=false;
bool backright=false;
auto backtrace=[&]() {
if (iter->parent->left==iter)
backleft=true, backright=false;
else
backright=true, backleft=false;
iter=iter->parent;
};
while(iter!=nullptr)
{
if (backleft)
// backtraced, current node and all left nodes are visited
if (iter->right!=nullptr)
iter=iter->right, backleft=false;
else
if (iter->parent==nullptr)
// completed, no right branch
break;
else
backtrace();
else if (backright)
if (iter==node) // move back from the right side of tree
break;
else
backtrace();
else
{
// visit the current node
cout<<"Visited: "<value<
backleft=false;
backright=false;
if (iter->left!=nullptr)
iter=iter->left;
else if (iter->right!=nullptr)
iter=iter->right;
else
// leaf, forced to back
backtrace();
}
}
} |
