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

class Solution {
  public:
//这题有两种做法。一种是暴力的中序遍历，把结果存储下来（应该是没有不存储结果就能提前在找到时返回的办法了。）然后去比对。但题目要求空间复杂度为O(1)，所以这种办法没法用。
//这种是分类法。我自己分了5类。
//1.是左孩子且是叶节点时（5），打印父节点（6）。
//2.是左孩子但不是叶节点时（6），如果有右孩子，打印右孩子。如果没右孩子，就打印父节点。
//3.是右孩子且是叶节点时（7），朝父节点进行递归（6）。
//4.是右孩子但不是叶节点,且自己的右孩子存在时（10），朝自己的右孩子进行递归（11）。
//5.若自己的右孩子不存在，则向父节点递归。（也就是，在3和5两种情况中，自己都是最右的）

//但根据评论区大佬来看是可以提炼成两类的：
//简明扼要一点吧；就两种情况：1）这个节点有右孩子，那下一个节点（根据中序遍历）肯定就是右孩子子树的最左边的叶节点；2）这个节点没有右孩子，那就往上走；如果这个节点是他父亲节点的左孩子，那就返回这个父亲节点；如果该节点是父亲节点的右孩子，那就一直往上走，直到找到那个满足是左孩子节点的父节点即可。
    TreeLinkNode* FindFirstOfMiddleOrderSequence(TreeLinkNode* current) {
        while (current->left != nullptr) {
            current = current->left;
        }
        return current;
    }

//参数中的bRightChild值指的是指定的原始节点的。而不是递归到的当前的这个pNode的。
    TreeLinkNode* solve(TreeLinkNode* pNode, bool bRightChild) {
        //处理递归到了根节点的情况。
        bool bRoot =!pNode->next; //如果不存在父节点，那pNode就是根节点。
        if (bRoot) {
            //在不存在右子树的情况，以及从右子树一路递归回来到了根节的情况，都说明已经无解了。
            if (pNode->right == nullptr || bRightChild)
                return nullptr;
            TreeLinkNode* current = pNode->right;
            //步进，直到找到右子树的最靠左的叶节点为止。
            return FindFirstOfMiddleOrderSequence(current);
        }
        TreeLinkNode* current = pNode;
        //满足这种情况，会需要一直向父节点递归。直到哪一次父节点本身不为右孩子为止。因为右孩子永远是最晚被递归的。如果父节点自己也是右孩子，说明父节点早已被递归过了。只有当父节点本身为左孩子时，返回它的父亲的值。
        bool bcurrentIsLeftChild = current->next->left == current ;
        bool bcurrentIsRightChild = current->next->right == current;
        if (bcurrentIsLeftChild)return current->next;
        if (bcurrentIsRightChild) {
            return solve(current->next, bRightChild);
        }
        return nullptr;
    }

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        bool bRoot = !pNode->next; //如果不存在父节点，那pNode就是根节点。
        if (bRoot) {
            TreeLinkNode* current = pNode->right;
            if(!current)
                return nullptr;
            //找到右子树的第一个中序遍历节点。
            return FindFirstOfMiddleOrderSequence(current);
        }

        bool bLeaf = (pNode->left == nullptr && pNode->right == nullptr && pNode);
        bool bLeftChild = pNode->next->left == pNode ;
        bool bRightChild = pNode->next->right == pNode;
        //叶+左孩子
        if (bLeaf && bLeftChild) {
            return pNode->next;
        }
        //非叶+左孩子
        if ((!bLeaf) && bLeftChild) {
            if(pNode->right)//如果存在右孩子
                return pNode->right;
            return pNode->next;
        }
        //非叶+右孩子，如果存在右子树，则找到它的中序遍历的第一个节点即可。
        if ((!bLeaf) && bRightChild) {
            if (pNode->right) {
                return FindFirstOfMiddleOrderSequence(pNode->right);
            }
        }
        //叶+右孩子，或者是非叶+右孩子，但本身没右孩子的情况，算半个叶节点。
        //也就是统称为“自己是右孩子，而且没有右孩子”，那就要不断向父节点递归了。
        return solve(pNode,bRightChild);

    };
};