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

/*
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 <cstdio>
#include <vector>
class Solution {
public:
    void inorder(TreeLinkNode* pNode, vector<TreeLinkNode*>& nodes){
        if(!pNode){
            return;
        }
        inorder(pNode->left, nodes);
        nodes.push_back(pNode);
        inorder(pNode->right, nodes);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
       vector<TreeLinkNode*> nodes;
       // 首先需要找到根结点
       if(!pNode){
        return nullptr;
       }
       TreeLinkNode* cur = pNode;
       while(cur->next){
        cur = cur->next;
       }
       inorder(cur, nodes);
       int i = 0;
       for(;i<nodes.size()-1;i++){
        if(nodes[i] == pNode){
            return nodes[i+1];
        }
       }
       if(nodes[nodes.size()-1] == pNode){
        return nullptr;
       }
       return nullptr;
    }
};

首先通过当前结点沿着树向上爬，找到根结点。

然后对整个二叉树进行中序遍历，并记录中序遍历的结果res.

对中序遍历结果进行遍历，寻找当前结点，返回当前结点的下一个结点。如果当前结点为末端节点，则返回nullptr.