int val;

struct TreeLinkNode *left;

struct TreeLinkNode *right;

struct TreeLinkNode *next;

TreeLinkNode(int x) :val(x), left(nullptr), right(nullptr), next(nullptr) {}

TreeLinkNode* GetNext(TreeLinkNode* pNode){

if(pNode == nullptr)

return nullptr;

TreeLinkNode *next = nullptr;

if(pNode->right != nullptr){

auto q = pNode->right;

while(q->left != nullptr){

q = q->left;

}

next = q;

}

else if(pNode->next != nullptr){

auto parent = pNode->next;

auto q = pNode;

while(parent != nullptr && parent->right == q){

parent = parent->next;

q = q->next;

}

next = parent;

}

return next;

}