题目描述：
某种二叉树的节点包含指向 左子树、右子树、父节点的 3 个指针，给定该二叉树中的某个节点 ，
返回它的中序遍历的下一个节点的指针。
分析：
节点(设为x) 中序遍历的下一个节点有以下可能：
1. 若x有右子树。则x的下一个节点为x右子树最左侧节点。如，2的下一个节点为8。
2. 若x没有右子树，又分为2种情况。
2.1 若x是父节点的左孩子。则x的父节点就是x的下一个节点。如，7的下一个节点是4。
2.2 若x是父节点的右孩子。则沿着父节点向上，直到找到一个节点的父节点的左孩子
是该节点，则该节点的父节点就是x的下一个节点。如，9的下一个节点是1。
在上溯 的过程中如果到了 根节点仍然 没有找到目标节点，则返回 NULL。
代码：
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 { 18 return NULL; 19 } 20 if(pNode->right != NULL) 21 { 22 TreeLinkNode* ptr = pNode->right; 23 TreeLinkNode* front = ptr; 24 while(ptr != NULL) 25 { 26 front = ptr; 27 ptr = ptr->left; 28 } 29 return front; 30 } 31 else if(pNode->next == NULL || pNode->next->left == pNode) 32 { 33 return pNode->next; 34 } 35 else 36 { 37 while(pNode->next != NULL && pNode == pNode->next->right) 38 { 39 pNode = pNode->next; 40 } 41 return pNode->next; 42 } 43 } 44 };