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

/*
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:
    vector<TreeLinkNode*> out;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        
        TreeLinkNode* root=pNode;
        TreeLinkNode* cur=pNode;
        while (root->next) {
            root=root->next;
        }
        InOrder(root);
        for (int i=0; out.size()-1; i++) {
            if (out[i]==cur) {
                return out[i+1];
            }
        }
        return NULL;
    }
    void InOrder(TreeLinkNode* root){
        if(root==NULL){
            return;
        }
        InOrder(root->left);
        out.push_back(root);
        InOrder(root->right);
    }
};

要想找到当前节点中序遍历的下一节点，一种最直观暴力的思路是根据这一节点可以重现整棵树中序遍历的结果，然后对中序遍历的结果进行遍历搜索，找到所给节点，并返回此节点的下一节点。

根据所给节点重现整棵树中序遍历的结果：根据此节点不停上溯找到树的根节点，再将根节点输入到中序遍历的函数中得到中序遍历结果。