b*********n
发帖数: 1258 | 1 给定一个二叉树的一个node，编程返回中序遍历的下一个node。如果最后一个，返回
null, 怎么做？ |
g*******y
发帖数: 1930 | 2 if(p->right){ // p 有右孩子
p = p->right;
while(p->left) p = p->left;
return p; //返回右孩子子树的最左的节点；
}
while( p->parent && p != p->parent->left){ //p不是左孩子
p = p->parent; //往上走，直到p是左孩子，或者p是根节点了
}
return p->parent; //如果是走到根节点了，说明是最后一个，return null
【在 b*********n 的大作中提到】
: 给定一个二叉树的一个node，编程返回中序遍历的下一个node。如果最后一个，返回
: null, 怎么做？
|
f*********r
发帖数: 68 | 3 这个是不是应该在没有右孩子的情况下, 直接返回父节点?
【在 g*******y 的大作中提到】
: if(p->right){ // p 有右孩子
: p = p->right;
: while(p->left) p = p->left;
: return p; //返回右孩子子树的最左的节点；
: }
: while( p->parent && p != p->parent->left){ //p不是左孩子
: p = p->parent; //往上走，直到p是左孩子，或者p是根节点了
: }
: return p->parent; //如果是走到根节点了，说明是最后一个，return null
|
g*******y
发帖数: 1930 | 4 不是的，如果p没有右孩子，但是p自己右孩子，需要一直往上走，直到p自己是左孩自
为止。
【在 f*********r 的大作中提到】
: 这个是不是应该在没有右孩子的情况下, 直接返回父节点?
|
f*********r
发帖数: 68 | 5 哦, 对! 我想错了.
【在 g*******y 的大作中提到】
: 不是的，如果p没有右孩子，但是p自己右孩子，需要一直往上走，直到p自己是左孩自
: 为止。
|
r****o
发帖数: 1950 | 6 这种二叉树的节点要是要是没有定义parent指针该怎么办呢？
【在 g*******y 的大作中提到】
: if(p->right){ // p 有右孩子
: p = p->right;
: while(p->left) p = p->left;
: return p; //返回右孩子子树的最左的节点；
: }
: while( p->parent && p != p->parent->left){ //p不是左孩子
: p = p->parent; //往上走，直到p是左孩子，或者p是根节点了
: }
: return p->parent; //如果是走到根节点了，说明是最后一个，return null
|
S*********u
发帖数: 106 | 7 给定root
【在 r****o 的大作中提到】
: 这种二叉树的节点要是要是没有定义parent指针该怎么办呢？
|
r****o
发帖数: 1950 | 8 什么意思，
怎么找parent呢?
【在 S*********u 的大作中提到】
: 给定root
|
z*******y
发帖数: 578 | 9 这个跟那个BST找后继节点一样，
在Introduction to Algorithm 那本书上讲的很清楚，大家去把BST那节看看吧。 很系
统，看了之后有关这类题目就都知道怎么做了 |
v******k
发帖数: 808 | |
f****4
发帖数: 1359 | 11 书上也用到了parent的吧
【在 z*******y 的大作中提到】
: 这个跟那个BST找后继节点一样，
: 在Introduction to Algorithm 那本书上讲的很清楚，大家去把BST那节看看吧。 很系
: 统，看了之后有关这类题目就都知道怎么做了
|
