/*
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) {
             TreeLinkNode* p = pNode->right;
             while(p->left) p = p->left;
             return p;
         } else if (pNode->next){
             TreeLinkNode* cur = pNode;
             TreeLinkNode* parent = pNode->next;
             while(parent && cur == parent->right) {
                 cur = parent;
                 parent = cur->next;
             }
             return parent;
         } else {
             return NULL;
         }
    }
};