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

/*

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:

    vector<TreeLinkNode *> list;

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {

        //首先先找到二叉树的最终根节点

        TreeLinkNode *TreeSaveNode=pNode;

        while(pNode->next!=NULL){

            pNode=pNode->next;

        }

        mid(pNode);

        int i;

        for(i=0;i<=list.size()-1;i+=1){

            if(list[i]==TreeSaveNode){

                break;

            }

        }

        if(i==list.size()-1){

            return NULL;

        }

        return list[i+1];

    }

    void mid(TreeLinkNode * TreeNode){

        if(TreeNode->left!=NULL){

            mid(TreeNode->left);

        }

        if(TreeNode!=NULL){

            list.push_back(TreeNode);

        }

        if(TreeNode->right!=NULL){

            mid(TreeNode->right);

        }

    }

};