题解 | #二叉树的下一个结点#
二叉树的下一个结点
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
题目隐含的第一个参数是二叉树（不用管），第二个参数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;
}
}
查看30道真题和解析
