二叉树的下一个结点

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

思路：分三种情况：

（1）当前结点有右子树，则其下一个结点就是右子树中的最左子结点；

（2）当前结点是其父结点的左子结点，则下一个为其父结点；

（3）当前结点既不是右子树，也不是是其父结点的左子结点，则沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点，若存在，则这个结点的父结点是我们要找的下一个结点，若不存在，则没有。

代码如下：

 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==nullptr)
17             return nullptr;
18         
19         if(pNode->right !=nullptr)
20         {
21             pNode=pNode->right;
22             while(pNode->left !=nullptr)
23             {
24                 pNode=pNode->left;
25             }
26             return pNode;
27         }
28         
29         while(pNode->next !=nullptr)
30         {
31             TreeLinkNode *pFather=pNode->next;
32             if(pFather->left==pNode)
33                 return pFather;
34             pNode=pNode->next;
35         }
36         return nullptr; 
37     }
38 };

可以画图理解。