第一种情况需要不断的向上回溯, 第二种情况下一个结点就是其父节点.
代码如下:
- /*
- 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 * rev;
- if(pNode==NULL)
- return NULL;
- if(pNode->right!=NULL)
- {
- rev=pNode->right;
- while(rev->left!=NULL)
- rev=rev->left;
- return rev;
- }
- else
- {
- if(pNode->next==NULL)
- {
- return NULL;
- }
- if(pNode->next->left==pNode)
- {
- return pNode->next;
- }
- rev=pNode;
- while(rev->next!=NULL&&rev==rev->next->right)
- {
- rev=rev->next;
- }
- return rev->next;
- }
- }
- };
来源: http://www.bubuko.com/infodetail-3374877.html