二叉树的下一个节点
给定一个二叉树和其中的一个节点，请找出中序遍历顺序的下一个节点并且返回。注意，树中的节点不仅包含左右子节点，同时包含指向父节点的指针。
一颗有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的指针用虚线表示。中序遍历序列为[d,b,h,e,i,a,f,c,g]
分析：
- 如果节点有右子节点，则右子节点的最左节点是该节点的下一个节点。例如，寻找b的下一个节点的过程（b有右子节点e，e的左子节点是h，且h是e的最左节点，h是b的下一个节点）
- 如果节点无右子节点，但该节点是父节点的左子节点，则父节点是该节点的下一个节点。例如，寻找d的下一个节点的过程（d无右子节点，d是父节点b的左子节点，则b是de的下一个节点）
- 如果节点无右子节点，且该节点是父节点的右子节点，则沿着父节点的指针向上遍历。例如，寻找i的下一个节点的过程（i的父节点e，e是其父节点b的右子节点，节点b是其父节点a的左子节点，节点a是节点i的下一个节点）
/*
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 == nullptr)
return nullptr;
/* 寻找结果 */
// 如果节点有右子节点，则右子节点的最左节点是该节点的下一个节点
// 如果节点无右子节点，但该节点是其父节点的左子节点，则父节点是该节点的下一个节点
// 如果节点无右子节点，且该节点是其父节点的右子节点，则沿着父节点向上遍历，满足XXX的父节点是其该节点的下一个节点
TreeLinkNode * res = nullptr;
if(pNode->right != nullptr)
{
TreeLinkNode* node_right = pNode->right;
while(node_right ->left != nullptr)
{
node_right = node_right->left;
}
res = node_right;
}
else if(pNode->next != nullptr)
{
// 当前节点和当前节点的父节点
TreeLinkNode * current = pNode;
TreeLinkNode * parent = pNode->next;
while(parent!=nullptr && current == parent->right)
{
current = parent;
parent = parent ->next;
}
res = parent;
}
return res;
}
};