w*u
2 楼
都快月底了。
h*n
3 楼
iterative in order traversal.
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
s*t
4 楼
我的都存掉了
【在 w***u 的大作中提到】
: 都快月底了。
【在 w***u 的大作中提到】
: 都快月底了。
w*x
5 楼
stack
m*y
6 楼
19号就算月底了？发这样的贴有啥意义？等等不就来了？
S*e
7 楼
多谢两位，大概写了一下，能帮们确认一下吗?
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
Node *findInOrderSuccessor(Node *root, Node *target){
Stack
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
8 楼
Isn't the answer leftmost node of target node's right child tree??
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
【在 S*******e 的大作中提到】
: glassdoor上看到的，这题如果有parent point还比较简单，
: 如果没有的话怎么整？
y*1
9 楼
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??
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
10 楼
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
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
11 楼
一会儿做做。
p*2
12 楼
想了一下。这题应该用recursion吧？
p*2
13 楼
写了一个练练手
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
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
14 楼
你好像忘了考虑当 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:
回 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
15 楼
没明白什么意思呀。给个例子？
【在 i**********e 的大作中提到】
: 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
: 回 subtree->parent)。
p*2
16 楼
当node 是subtree的最右边值，我会返回node的。告诉上边我找到node了，但是没找到
next。
如果这个subtree恰好是上一层的左数，那就返回上一层的node，不然继续返回node往
上走。
【在 i**********e 的大作中提到】
: 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
: 回 subtree->parent)。
i*e
17 楼
呵呵，少看了一个条件。没事，你是考虑了这个条件的。
另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
程序
每次要从root 开始.
只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
stack，没必要搞得那么复杂。
另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
程序
每次要从root 开始.
只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
stack，没必要搞得那么复杂。
p*2
18 楼
例如，一个 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
19 楼
不好意思，你是对的。
是next inorder，所以不看left subtree。
主要看有没有right child，有的话返回right subtree的 left most node。不然的话
得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
stack（非递归） 来做。
是next inorder，所以不看left subtree。
主要看有没有right child，有的话返回right subtree的 left most node。不然的话
得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
stack（非递归） 来做。
Z*Z
20 楼
响应大侠号召。写了个直白板的，求拍。
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，没必要搞得那么复杂。
static
if(tree == null){
return null;
}
if(node.right != null){
Node
while(tmp.left != null){
tmp = tmp.left;
}
return tmp;
}
Stack
if(!searchNode(tree, node, stk)){
return null;
}
Node
while(!stk.isEmpty()){
Node
if(child == parent.left){
return parent;
}
child = parent;
}
return null;
}
static
de, Stack
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
21 楼
这样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:
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
22 楼
好像没问题，至少我没看出来
【在 S*******e 的大作中提到】
: 这样recrusion好像是对的，不过像我前面那样直接用
: stack iterative in-order traversal好像更简单啊。
: 我的做法有问题吗？
: http://www.mitbbs.com/article/JobHunting/32160147_0.html
【在 S*******e 的大作中提到】
: 这样recrusion好像是对的，不过像我前面那样直接用
: stack iterative in-order traversal好像更简单啊。
: 我的做法有问题吗？
: http://www.mitbbs.com/article/JobHunting/32160147_0.html
p*2
23 楼
stack是正确的解法。leetcode已经总结了。不过我看到这题的第一感觉就是dfs，所以
就写出来了。这个跟个人的思维习惯有关系，我做dfs比较熟。
【在 S*******e 的大作中提到】
: 这样recrusion好像是对的，不过像我前面那样直接用
: stack iterative in-order traversal好像更简单啊。
: 我的做法有问题吗？
: http://www.mitbbs.com/article/JobHunting/32160147_0.html
p*2
24 楼
嗯。leetcode总结的很好。这个优化应该有。
【在 i**********e 的大作中提到】
: 不好意思，你是对的。
: 是next inorder，所以不看left subtree。
: 主要看有没有right child，有的话返回right subtree的 left most node。不然的话
: 得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
: stack（非递归） 来做。
S*e
25 楼
哦，多谢
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
i*e
26 楼
小心别把面试官给震经了。
２爷：
“这么简单的题我一向来都是直接上ｄｆｓ的！”
面试官直接跪了。。。
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
２爷：
“这么简单的题我一向来都是直接上ｄｆｓ的！”
面试官直接跪了。。。
【在 p*****2 的大作中提到】
:
: 嗯。leetcode总结的很好。这个优化应该有。
w*x
27 楼
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;
};
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
};
p*2
28 楼
刚开始我以为写个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
29 楼
刚开始我以为写个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
30 楼
滔滔江水连绵不绝，黄河泛滥一发不可收拾啊~~
【在 p*****2 的大作中提到】
:
: 刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。
p*2
31 楼
看你整天说没题可做了。感觉很膜拜你。
【在 w****x 的大作中提到】
:
: 滔滔江水连绵不绝，黄河泛滥一发不可收拾啊~~
相关阅读
United MileagePlus Explorer 怎么加不到chase的账户上UA 还是 US往返段不是一个联盟的飞机,如何积累里程请问citi thankyou preferred卡是不是没有amex的？急问这些店哪些属于citi 5%的electronic store?citi thankyou points买票这么值钱吗请问信用卡是charge-off应该怎么解决？谢谢请问大家chase 5% Gas第一月账单已出仍未收到SPG开户点请问barclay在texas pull哪家？discover 2% cb on Oct. 6 买iphone划算吗？大家请拍我，关于400bonus的barclay ccDiscover关于Oct 6 2%的答复AMEX的点数转Delta里程现在还有捐款刷卡的地方么通过 UR Mall 在 Sears的Marketplace购物 能拿到10倍返点吗现在把 信用卡上的钱 变成 CASHC1 premier rewards checking 怎么样？从BOA往国内汇款看了俺贴子买mypoints/opensky东西的