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

/*
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 <sys/types.h>
#include <vector>
class Solution {

public:
    vector<TreeLinkNode*> nodes;

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* root = pNode;
        if(root == nullptr) return nullptr;
        // 找根节点 因为next指针指向父节点
        while(root->next != nullptr)
        {
            root = root->next;
        }
        // 中序遍历
        InOrder(root);
        for(int i = 0; i < nodes.size(); i ++)
        {
            if(nodes[i] == pNode) return nodes[i + 1];
        }
        return nullptr;
    }
    void InOrder(TreeLinkNode* root)
    {
        if(root == nullptr) return;
        InOrder(root->left);
        nodes.push_back(root);
        InOrder(root->right);
    }
};