剑指offre之【二叉树的下一个节点】

题目：

　　二叉树的下一个结点

链接：

　　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 };