57、剑指offer--二叉树的下一结点

 1 /*
 2 struct TreeLinkNode {
 3     int val;
 4     struct TreeLinkNode *left;
 5     struct TreeLinkNode *right;
 6     struct TreeLinkNode *next;
 7     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
 8          
 9     } 
10 };
11 */
12 class Solution {
13 public:
14     TreeLinkNode* GetNext(TreeLinkNode* pNode)
15     {
16         if(pNode == NULL)
17             return NULL;
18         TreeLinkNode *pNext = NULL;
19         //有右结点，其下一结点为右结点的最左子结点
20         if(pNode->right != NULL)
21         {
22             TreeLinkNode *pRight = pNode->right;
23             while(pRight->left != NULL)
24                 pRight = pRight->left;
25             pNext = pRight;
26         }
27         //无右结点
28         else
29         {
30             TreeLinkNode *pCurrent = pNode;
31             TreeLinkNode *pParent = pNode->next;
32             while(pParent != NULL && pCurrent == pParent->right)//是父结点的右子结点，沿父结点一直向上查找
33             {
34                 pCurrent =pParent;
35                 pParent = pParent->next;
36             }
37             pNext = pParent;
38         }
39         return pNext;
40     }
41 };