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

这也是时间O(n)，空间O(1)的解法啊

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:
    void help(TreeLinkNode* root,TreeLinkNode* pNode,TreeLinkNode* &res,bool &flag){
        //root是当前节点，pNode是题目给出节点，res是结果节点，
        if(root==NULL) return ;
        help(root->left,pNode,res,flag);
        if(flag){
            res=root;
            flag=false;
            return ;
        }
        if(root==pNode) flag=true;
        help(root->right,pNode,res,flag);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* root=pNode,*res=NULL;
        while(root->next!=NULL) root=root->next;
        bool flag=false,flag1=false;
        help(root,pNode,res,flag);
        return res;
    }
};