本文共 1315 字，大约阅读时间需要 4 分钟。

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

/*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==NULL){            return NULL;        }        //1.判断有没有右子树，pNode节点有右孩子,下一个结点就是以pNode结点的右孩子为根的子树中的最左下结点。        if(pNode->right!=NULL){            pNode=pNode->right;            //当左子树不为空时一直往下遍历            while(pNode->left!=NULL){                pNode=pNode->left;            }            return pNode;        }//2.pNode节点没有右孩子时，pNode节点是其父结点的左孩子,直接将父节点返回.        if(pNode->next==NULL){            return NULL;        }        if(pNode==pNode->next->left){            return pNode->next;//返回父节点        }//3.pNode节点没有右孩子时，pNode节点是其父结点的右孩子,需要不断的向上移动，直到父节点是其父节点的父节点的左孩子//既然他是父节点的左节点，此时将这个节点父节点返回即可，或者遍历到了根节点，返回null.        TreeLinkNode* pNext = pNode->next;        while(pNext->next!=NULL){            //父节点不为空时            if(pNext==pNext->next->left)            {//找到一个父节点的左子节点的节点，返回这个节点的父节点                return pNext->next;            }        //继续向上找父节点            pNext = pNext->next;        }        //走到这，父节点为空        return NULL;    }};

转载地址：http://bqypi.baihongyu.com/