题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
结题思路：
首先题目要求是中序遍历顺序，那么就是左根右的顺序。再求下一个结点的过程中，我们需要分情况讨论：
1、该结点有右子树，则该结点的下一个结点即为该结点右子树前序遍历下的第一个结点，也就是最左边的结点。
2、该结点没有右子树，则又分两种情况讨论：
（1）该结点为其父结点的左孩子，则其父结点为下一个结点。
（2）该结点为其父结点的右孩子，则其该结点所属的最小左子树的父结点为下一个结点。
/* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode == NULL) return NULL; if(pNode->right){ //如果节点存在右子树，则下一个节点就是右子树最左边的结点 pNode = pNode->right; while(pNode->left) pNode = pNode->left; return pNode; } while(pNode->next){ //没有右子树，则下一个节点是其所属的最小左子树的父结点 if(pNode->next->left == pNode) return pNode->next; pNode = pNode->next; } return NULL; } };
