给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。...

/*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=pNode; if(pNode->right!=NULL)//节点有有孩子 { p=pNode->right; while(p->left) p=p->left; return p; } else {//节点无右孩子 if(pNode->next!=NULL)//有父亲 { if(pNode->next->right==pNode)//节点是父亲的右孩子时 { if(pNode->next->next!=NULL&&pNode->next->next->left==pNode->next)//如果父节点是祖父的左孩子       return pNode->next->next;//返回祖父 else       return NULL; } if(pNode->next->left==pNode)//如果父节点是左孩子 return pNode->next;//返回父节点 } else{ return NULL; } }

转载于:https://www.cnblogs.com/yuanch2019/p/11585280.html