题目隐含的第一个参数是二叉树(不用管),第二个参数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; } }