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

/*
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 <vector>
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(pNode == nullptr)
        {
            return nullptr;
        }
        TreeLinkNode* root = pNode;
        while (root->next) {
            root = root->next;
        }
        vector<TreeLinkNode*> vecRes;
        midTree(root,vecRes);
        for(int i = 0; i < vecRes.size(); ++i)
        {
            if(vecRes[i] == pNode)
            {
                return vecRes[i+1];
            }
        }
        return nullptr;
    }

    void midTree(TreeLinkNode* node, vector<TreeLinkNode*>& res)
    {
        if(node == nullptr)
        {
            return;
        }
        midTree(node->left,res);
        res.push_back(node);
        midTree(node->right,res);
    }

};

1、找到根节点

2、中序遍历

2、返回输入节点的下一个节点