题解 | #二叉树的下一个结点#

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
#include <cstddef>
#include <vector>
class Solution {
  public:
    //vector<TreeLinkNode*> nodes;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (pNode == NULL) return NULL;
        TreeLinkNode* root = pNode;
        while (root->next) {
            root = root->next;
        } // 完成while循环后，root即指向根结点
        vector<TreeLinkNode*> nodes;
        InOrder(nodes, root);
        vector<TreeLinkNode*>::iterator it = std::find(nodes.begin(), nodes.end(), pNode);
        if(*(it+1) != NULL) return *(it+1);
        else return NULL;
    }

    void InOrder(vector<TreeLinkNode*>& nodes, TreeLinkNode* root) {
        if (root == NULL) return;
        InOrder(nodes, root->left);
        nodes.push_back(root);
        InOrder(nodes, root->right);
    }
};