题目：

　　二叉树的下一个结点

链接：

　　https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目描述：

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

思路：

　　在当前结点下：

　　　　如果有右节点，则下一个结点一定在当前结点的右子树中，且下一个结点的左子树为空；

　　　　如果没有右节点，则下一个结点一定在当前结点的父辈之中，且下一个节点的左子树一定是该节点的父辈；

代码：

　　

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         if(pNode ->right != nullptr){19             pNode = pNode->right;20             while(pNode->left != nullptr){21                 pNode = pNode->left;22             }23             return pNode;24         }25         while (pNode->next != nullptr){26             if(pNode->next->left  == pNode){27                 return pNode->next;28             }29             pNode = pNode->next;30         }31         return nullptr;32     } 33 };