自己写的
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL)
return NULL;
if(pNode->right != NULL){
TreeLinkNode* origin = pNode->right;
while(origin->left != NULL)
origin = origin->left;
return origin;
}
else{
TreeLinkNode* father = pNode->next;
if(father != NULL){
if(father->left == pNode)
return father;
while(father != NULL && father->right == pNode){
pNode = father;
father = pNode->next;
}
}
return father;
}
}
};father != NULL && father->right == pNode这个前后顺序不能换，换了就会报以下错误：
段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起 书上的写法：
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { }
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL)
return NULL;
if(pNode->right != NULL){
TreeLinkNode* next = pNode->right;
while(next->left != NULL){
next = next->left;
}
return next;
}
else{
TreeLinkNode* nextone = pNode;
TreeLinkNode* father = pNode->next;
while(father != NULL && father->left != nextone){
nextone = father;
father = nextone->next;
}
return father;
}
}
};
father != NULL一定要注意，这种情况一个是让father->left能不报错，还有一个就是解决了一个bad case，就是这个结点就是最后一个结点就返回NULL，或者说万一父结点全是右子树的