S*******e
发帖数: 379 | 1 glassdoor上看到的，这题如果有parent point还比较简单，
如果没有的话怎么整？ |
h*******n
发帖数: 614 | 2 iterative in order traversal.
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
|
w****x
发帖数: 2483 | |
S*******e
发帖数: 379 | 4 多谢两位，大概写了一下，能帮们确认一下吗?
Node *findInOrderSuccessor(Node *root, Node *target){
Stack s;
Node *cur = root;
Node *prev = NULL;
while(true){
while(cur) {
s.push(cur);
cur = cur->left;
}
if (s.empty()){
break;
} else {
cur = s.pop();
}
if (prev == target) {
return cur;
}
prev = cur;
cur = cur->right;
}
return NULL;
}
【在 w****x 的大作中提到】
: stack
|
y****g
发帖数: 5 | 5 Isn't the answer leftmost node of target node's right child tree??
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
|
y***1
发帖数: 450 | 6 I think that's the answer, but you have to handle the case when the node
does not have right node. In that case, use breadth-first traversal.
【在 y****g 的大作中提到】
: Isn't the answer leftmost node of target node's right child tree??
|
t********3
发帖数: 567 | 7 if this node has right subtree, get the min node from that.
if not, travel from root node to current node, store the path in some kind
of list/or stack etc. iterate back according to the list/stack, the
successor is the first right parent node |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 10 写了一个练练手
def first(root):
if root!=None:
l=first(root.left)
if l: return l
return root
def dfs(root,node):
if root==None: return root
if root==node:
r=first(root.right)
return r if r else root
else:
l=dfs(root.left,node)
if l: return l if l!=node else root
else: return dfs(root.right,node)
def next(root,node):
ret=dfs(root,node)
return ret if ret!=node else None |
|
|
i**********e
发帖数: 1145 | 11 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
回 subtree->parent)。
【在 p*****2 的大作中提到】
: 写了一个练练手
: def first(root):
: if root!=None:
: l=first(root.left)
: if l: return l
: return root
: def dfs(root,node):
: if root==None: return root
:
: if root==node:
|
p*****2
发帖数: 21240 | 12
没明白什么意思呀。给个例子？
【在 i**********e 的大作中提到】
: 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
: 回 subtree->parent)。
|
p*****2
发帖数: 21240 | 13
当node 是subtree的最右边值，我会返回node的。告诉上边我找到node了，但是没找到
next。
如果这个subtree恰好是上一层的左数，那就返回上一层的node，不然继续返回node往
上走。
【在 i**********e 的大作中提到】
: 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
: 回 subtree->parent)。
|
i**********e
发帖数: 1145 | 14 呵呵，少看了一个条件。没事，你是考虑了这个条件的。
另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
程序
每次要从root 开始.
只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
stack，没必要搞得那么复杂。 |
p*****2
发帖数: 21240 | 15
例如，一个 node 如果有 left node，直接返回 left-most node 即可
>>这个不是inorder吗？怎么会直接返回left-most?
只有在 node 是 leaf node 的情况之下 才需要从 root 开始
>>如果node没有right node的话也需要从root开始呀。
感觉只在node有right的情况呀，才能能直接返回吧？这种情况应该可以wrap一下就包
括了吧。一会儿看看。
【在 i**********e 的大作中提到】
: 呵呵，少看了一个条件。没事，你是考虑了这个条件的。
: 另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
: 问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
: 程序
: 每次要从root 开始.
: 只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
: stack，没必要搞得那么复杂。
|
i**********e
发帖数: 1145 | 16 不好意思，你是对的。
是next inorder，所以不看left subtree。
主要看有没有right child，有的话返回right subtree的 left most node。不然的话
得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
stack（非递归） 来做。 |
Z*****Z
发帖数: 723 | 17 响应大侠号召。写了个直白板的，求拍。
static >Node next(Node tree, Node node) {
if(tree == null){
return null;
}
if(node.right != null){
Node tmp = node.right;
while(tmp.left != null){
tmp = tmp.left;
}
return tmp;
}
Stack> stk = new Stack>();
if(!searchNode(tree, node, stk)){
return null;
}
Node child = stk.pop();
while(!stk.isEmpty()){
Node parent = stk.pop();
if(child == parent.left){
return parent;
}
child = parent;
}
return null;
}
static > boolean searchNode(Node tree, Node no
de, Stack> stk){
if(tree == null){
return false;
}
stk.push(tree);
if(tree == node ||
searchNode(tree.left, node, stk) ||
searchNode(tree.right, node, stk)){
return true;
}
stk.pop();
return false;
}
【在 i**********e 的大作中提到】
: 呵呵，少看了一个条件。没事，你是考虑了这个条件的。
: 另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
: 问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
: 程序
: 每次要从root 开始.
: 只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
: stack，没必要搞得那么复杂。
|
S*******e
发帖数: 379 | 18 这样recrusion好像是对的，不过像我前面那样直接用
stack iterative in-order traversal好像更简单啊。
我的做法有问题吗？
http://www.mitbbs.com/article/JobHunting/32160147_0.html
【在 p*****2 的大作中提到】
: 写了一个练练手
: def first(root):
: if root!=None:
: l=first(root.left)
: if l: return l
: return root
: def dfs(root,node):
: if root==None: return root
:
: if root==node:
|
j********e
发帖数: 1192 | 19 好像没问题，至少我没看出来
【在 S*******e 的大作中提到】
: 这样recrusion好像是对的，不过像我前面那样直接用
: stack iterative in-order traversal好像更简单啊。
: 我的做法有问题吗？
: http://www.mitbbs.com/article/JobHunting/32160147_0.html
|
p*****2
发帖数: 21240 | 20
stack是正确的解法。leetcode已经总结了。不过我看到这题的第一感觉就是dfs，所以
就写出来了。这个跟个人的思维习惯有关系，我做dfs比较熟。
【在 S*******e 的大作中提到】
: 这样recrusion好像是对的，不过像我前面那样直接用
: stack iterative in-order traversal好像更简单啊。
: 我的做法有问题吗？
: http://www.mitbbs.com/article/JobHunting/32160147_0.html
|
|
|
p*****2
发帖数: 21240 | 21
嗯。leetcode总结的很好。这个优化应该有。
【在 i**********e 的大作中提到】
: 不好意思，你是对的。
: 是next inorder，所以不看left subtree。
: 主要看有没有right child，有的话返回right subtree的 left most node。不然的话
: 得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
: stack（非递归） 来做。
|
S*******e
发帖数: 379 | 22 哦，多谢
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
|
i**********e
发帖数: 1145 | 23 小心别把面试官给震经了。
２爷：
“这么简单的题我一向来都是直接上ｄｆｓ的！”
面试官直接跪了。。。
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
|
w****x
发帖数: 2483 | 24 5 minutes
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.push(pNode);
pNode = pNode->pLft;
}
}
private:
stack m_stk;
}; |
p*****2
发帖数: 21240 | 25
刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。
【在 w****x 的大作中提到】
: 5 minutes
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;
: NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
: };
: class BTIterator
: {
|
p*****2
发帖数: 21240 | 26
刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。
【在 w****x 的大作中提到】
: 5 minutes
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;
: NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
: };
: class BTIterator
: {
|
w****x
发帖数: 2483 | 27
滔滔江水连绵不绝，黄河泛滥一发不可收拾啊~~
【在 p*****2 的大作中提到】
:
: 刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。
|
p*****2
发帖数: 21240 | 28
看你整天说没题可做了。感觉很膜拜你。
【在 w****x 的大作中提到】
:
: 滔滔江水连绵不绝，黄河泛滥一发不可收拾啊~~
|
