解法一：暴力解法

据题意，「某结点的下一个结点」定义为「中序遍历」后的下一个结点。因此暴力解法的步骤为：

  1. 根据输入的结点以及next指针，先求得二叉树的根结点root；
  2. 利用root进行二叉树的中序遍历，并定义数组储存中序遍历的结果；
  3. 遍历该数组，得到「下一个结点」。

注意：二叉树的中序遍历步骤为：先遍历左子树，再访问根结点，再遍历右子树。因此可通过递归较为方便地实现二叉树的中序遍历。

代码如下：

/*
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) 
            return NULL;
        // 寻找根结点
        TreeLinkNode* root = pNode;
        while (root->next) {
            root = root->next; 
        } // 完成while循环后，root即指向根结点
        vector<TreeLinkNode*> nodeVec; 
        inorder(root, nodeVec); // 中序遍历
        for (int i = 0; i < nodeVec.size(); i ++) {
            if (nodeVec[i] == pNode && i + 1 < nodeVec.size())
                return nodeVec[i + 1]; // 下一个结点为所求结点
        }
        return NULL; // 若该结点无下一结点，返回NULL
    }
    void inorder(TreeLinkNode* root, vector<TreeLinkNode*> &nodeVec) {
        if (!root)
            return; 
        inorder(root->left, nodeVec); // 访问左子树
        nodeVec.push_back(root);  // 访问根结点
        inorder(root->right, nodeVec); // 访问右子树
    }
};

在进行中序遍历时，遍历到树的所有结点，因此复杂度为O(N)；在进行数组遍历时，复杂度为O(N)，故总时间复杂度为O(N)。

此解法定义数组存储中序遍历结果，故空间复杂度为O(N)。

解法二：利用中序遍历性质

解法一进行了一整个中序遍历，然而题目仅要求「下一个结点」，因此进行「整个」中序遍历是不必要的。

解法二的思路利用了中序遍历的性质。中序遍历的步骤可表示为LTR，其中L代表左子树，T代表根结点，R代表右子树，即：先访问某结点的左子树，再访问该结点，再访问该结点的右子树。

「某结点的下一个结点」仅有二种情况：

  1. 若该结点存在右子树，则「下一个结点」为「该结点右子树的最左孩子」；
  2. 若该结点不存在右子树，则「下一个结点」为「该结点的第一个右父结点」。

下面结合图例分别对上述二种情况进行阐述。

对于情况一，步骤如下：

  1. 结点1存在右子树，则在进行中序遍历时，在访问结点1后，必将访问「该结点的右子树」，即以2为根结点的子树。
  2. 在访问该子树时，会先访问结点2的左子树，即以3为根结点的子树。
  3. 在访问该子树时，会先访问结点3的左子树，即结点4。

图片说明

以此类推，在通过中序遍历访问某结点的右子树时，会从其「右子树的最左孩子开始」。

对于情况二，步骤如下：

  1. 结点1不存在右子树，则其『下一个结点』，设为p，一定满足条件：结点1位于p结点的左子树上。因此，需要寻找其第一个「右父亲」；
  2. 结点1不存在右父亲，故向上寻找，即寻到结点2；
  3. 结点2不存在右父亲，故向上寻找，即寻到结点3；
  4. 结点3的右父亲为结点4。结点4即为所求。可见，待求结点（结点1）位于结点4的左子树上。

图片说明

故得出结论：若该结点不存在右子树，则「下一个结点」为「该结点的第一个右父结点」。

代码如下：

/*
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)
            return NULL;
        // 若该结点存在右子树
        if (pNode->right) {
            TreeLinkNode* rightChild = pNode->right; 
            // 寻找右子树上的最左孩子
            while (rightChild->left)
                rightChild = rightChild->left;
            return rightChild;
        }
        // 若不存在右子树，寻找第一个右父亲
        while (pNode->next) {
            if (pNode->next->left == pNode) 
                return pNode->next; 
            pNode = pNode->next;
        }
        return NULL;
    }
};

该方法最坏情况如图所示，对于1号结点，需要不断向上寻找其第一个右父亲，故需要遍历整棵树，时间复杂度为O(N)；该方法不需要引入额外空间，空间复杂度为O(1)。
图片说明