题目描述
- 给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？
- 树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针
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){
TreeLinkNode *p, *c, *next;
if(pNode == NULL){
return NULL;
}
// 如果该节点有右子树
if(pNode->right != NULL){
p = pNode->right;
while(p->left != NULL){
p = p->left;
}
next = p;
} // 执行 else if 证明该节点没有右子树
else if(pNode->next != NULL){
p = pNode->next;
c = pNode;
while(p!=NULL && c == p->right){
c = p;
p = p->next;
}
next = p;
}
return next;
}
};
总结展望
- 看书思路不难，容易理解，然后自己手写了；但是，我认为我的代码没问题，没想到提交到牛客网报错为
段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起，实在是不知道为啥，留待以后第二遍再来解决吧...
(出错代码在下面已更正 2019/3/3)
- 上面跑正确这个代码是参考别人正确代码写的，写的确实不错，比我的简洁！
附录
- 自己手动写的出错代码，有待修改
段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
// 因为指针为空，出错代码
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode){
TreeLinkNode *p;
if(pNode == NULL){
return NULL;
}
//１，节点有右子树
if(pNode->right != NULL){
p = pNode->right;
//现在两种情况
// 1.1 右子树没有左节点，则右子树根节点即为中序遍历下一个节点
if(p->left == NULL){
return p;
}
else{ // 1.2 右子树有左节点，则沿着右子节点出发一直沿着指向左子节点的指针行进
while(p->left != NULL){
p = p->left;
}
return p;
}
}
else // ２ 节点没有右子树
{ // 2.1 节点是它父节点的的左子节点，那么它的下一个节点就是它的父节点
p = pNode->next;
if(pNode == p->left){ // 如果p为空呢，这就是出错点，指针为空，下面为修改之后代码
return pNode->next;
}
else // 2.2 如果一个节点既没有右子树，并且它还是它父节点的右子节点，
{ //那么沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点
while(pNode->next != NULL){
p = pNode->next;
if(p->left == pNode){
return p;
}
pNode = pNode->next;
}
return NULL;
}
}
}
};
// 更正之后的代码
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode){
TreeLinkNode *p;
if(pNode == NULL){
return NULL;
}
//１，节点有右子树
if(pNode->right != NULL){
p = pNode->right;
//现在两种情况
// 1.1 右子树没有左节点，则右子树根节点即为中序遍历下一个节点
if(p->left == NULL){
return p;
} // 1.2 右子树有左节点，则沿着右子节点出发一直沿着指向左子节点的指针行进
else {
while(p->left != NULL){
p = p->left;
}
return p;
}
}
else { // ２ 节点没有右子树
p = pNode->next;
if(p != NULL){
// 2.1 节点是它父节点的的左子节点，那么它的下一个节点就是它的父节点
if(pNode == p->left){
return pNode->next;
}
else // 2.2 如果一个节点既没有右子树，并且它还是它父节点的右子节点，
{ //那么沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点
while(pNode->next != NULL){
p = pNode->next;
if(p->left == pNode){
return p;
}
pNode = pNode->next;
}
return NULL;
}
}
else{
return p;
}
}
}
};
