二叉树中序遍历的下一个结点

写在前面

剑指offer：二叉树的下一个结点

题目要求

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解法

/*
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:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(!pNode||(!pNode->right&&!pNode->next)) return nullptr;
        TreeLinkNode* cur = pNode;
        if(pNode->right) {
            cur = pNode->right;
            while(cur->left) {
                cur = cur->left;
            }
            return cur;
        }
        else if(pNode->next->left==pNode)
            return pNode->next;
        else if(pNode->next->right==pNode) {
            cur = pNode->next;
            while(cur&&cur->next&&cur==cur->next->right) {
                cur = cur->next;
            }
            return cur->next;
        }
        return nullptr;
    }
};

分析：
分类讨论：
特殊情况：如果当前结点为空或者当前结点的右孩子且父亲结点都不存在则该结点为中序遍历的最后一个结点，即没有后续结点返回nullptr.
当当前结点有右孩子则中序遍历的下一个结点是其右子树的最左结点。
当当前结点没有右子树的时候，如果当前结点是其父亲结点的左孩子，说明其父亲结点还未被访问，所以下一个结点就是其父亲节点。如果当前结点是其父亲结点的右孩子，说明父亲结点已经被访问过了，所以需要往上找到第一个不是其父亲结点右孩子的结点，直到向上到根为止。