二叉树的下一个节点

题目描述

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

问题分析

如果一个结点有右子树，那么它的下一个结点就是它的右子树中的最左子结点；
如果给定结点是其父结点的左子结点，那么它的下一个结点就是它的父结点；
如果一个结点既没有右子树，并且它还是它父结点的右子结点，那我们就需要一直向上遍历，知道找到一个是其父结点的左子结点的结点。

解题思路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:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        /*
        1.边界判断
        2.如果存在右子树,则下一个节点为右子树的最左子树
        3.如果不存在，则一直往父节点找，直到当前节点为父节点的左子树，这样下一个节点就是这个当前的父节点
        */
        //注意别声明为野指针
        TreeLinkNode* pNextNode = NULL;
        if (pNode == NULL)
        {
            return pNextNode;
        }
        if (pNode->right != NULL)
        {
            //pNextNode = pNode->right;
            TreeLinkNode* pRight = pNode->right;
            while (pRight->left != NULL)
            {
                pRight = pRight->left;
            }
            pNextNode = pRight;
        }
        else if (pNode->next != NULL)
        {

            TreeLinkNode* pCurrent = pNode;
            TreeLinkNode* pParrent = pNode->next;
            //注意判断当前节点是否为其父节点的右子树
            while (pParrent != NULL  && pCurrent == pParrent->right)
            {
                //更新
                pCurrent = pParrent;
                pParrent = pParrent->next;

            }
            pNextNode = pParrent;
        }

        return pNextNode;

    }
};