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

class Solution {
public:

    int flag = 0;   
    struct TreeLinkNode* res;  //返回值
    struct TreeLinkNode* son;   //记录给出的子树根节点

    void bianli(TreeLinkNode* p){   //中序遍历
        if(p->left != NULL) bianli(p->left);
        if(flag == 1) {     //flag==1  说明这个节点就是要输出的节点
            res = p;   //记录
            flag = 0;   //置flag为0  防止下一个节点更新掉当前节点
        }
        if(p == son) flag = 1;   //如果当前节点是给出的节点，则表明下一个节点要输出，flag置1
        if(p->right != NULL) bianli(p->right);
        return ;
    }

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        son = pNode;
        struct TreeLinkNode* root = pNode;
        while(root->next != NULL) root = root->next;   //root用来找到根节点
        bianli(root);
        return res;
    }
};
//递归方法时空复杂度都是On   如果要满足要求就考虑所有情况然后判断，不同情况找不同节点即可