题目隐含的第一个参数是二叉树(不用管),第二个参数pNode指向二叉树中的一个结点,题目要返回pNode结点在这个二叉树的中序遍历下一个结点地址。
因为中序遍历是左->根->右(简单点就是把树看成整体,不管结点父子关系,按结点从左到右出现的顺序遍历),所以分两种情况讨论:
一:当pNode有右结点时,找到其右结点,并找该右结点的最深左孩子结点(先右一次再左到底),返回最深左结点。
二:当pNode没有右结点时,它的下一个结点为它右边的结点,这个结点如果有只会出现在它的父结点中,只要pNode不在它的父结点的右孩子中,就输出该父结点。
/**
* struct TreeLinkNode {
* int val;
* struct TreeLinkNode *left;
* struct TreeLinkNode *right;
* struct TreeLinkNode *next;
* };
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pNode TreeNode类
* @return TreeNode类
*/
struct TreeLinkNode* GetNext(struct TreeLinkNode* pNode ) {
// write code here
struct TreeLinkNode *p=pNode,*q;
if(p->right!=0){//为非叶结点且有右孩子
p=p->right;
while(p->left){
p=p->left;
}
return p;
}
else{//为叶结点或者只有左孩子
while(p->next){
q=p;
p=p->next;
if(p->right!=q){
return p;
}
}
return NULL;
}
}

京公网安备 11010502036488号