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

思路：

中序遍历中

有右子树，就是其右子树的下一个结点， 比如结点5的下一个结点是7

没右子树，是其父亲的左子树，下一个结点是其父亲，比如结点9的下一个结点是4

没右子树，是父亲的右子树，下一个节点是当前节点所在左子树根，比如结点2的下一个结点是3

#include <iostream>

using namespace std;


struct TreeLinkNode
{
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;

    TreeLinkNode(int x = 0)
        :val(x), left(NULL), right(NULL), next(NULL) {

    }
};

class Solution
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (pNode == NULL) {
            return NULL;
        }

        TreeLinkNode *pNext = NULL;
        //当前节点有右子树，那么中序遍历的下一个结点就是其右子树的最左结点
        if (pNode->right != NULL) {
            pNext = pNode->right;
            while (pNext->left != NULL) {
                pNext = pNext->left;
            }
        }
		
        else if (pNode->right == NULL && pNode->next != NULL) {
            TreeLinkNode *pCurrent = pNode;
            TreeLinkNode *pParent = pNode->next;
		//没有右子树，是父亲的左子树，下一个结点就是父结点
            
        //没右子树，是父亲的右子树，下一个结点是当前结点所在左子树的根
        //顺着父结点一直向上遍历，直到找到一个它父结点所在左子数的根
            while (pParent != NULL && pCurrent == pParent->right) {
                pCurrent = pParent;
                pParent = pParent->next;
            }
            pNext = pParent;
        }

        return pNext;
    }
};

int main()
{
    Solution solu;
    TreeLinkNode tree[10];
    tree[0].val = 3;
    tree[0].left = &tree[1];
    tree[0].right = &tree[2];
    tree[0].next = NULL;


    tree[1].val = 6;
    tree[1].left = &tree[3];
    tree[1].right = &tree[4];
    tree[1].next = &tree[0];


    tree[2].val = 5;
    tree[2].left = NULL;
    tree[2].right = &tree[5];
    tree[2].next = &tree[0];


    tree[3].val = 4;
    tree[3].left = &tree[6];
    tree[3].right = NULL;
    tree[3].next = &tree[1];

    tree[4].val = 2;
    tree[4].left = NULL;
    tree[4].right = NULL;
    tree[4].next = &tree[1];

    tree[5].val = 7;
    tree[5].left = &tree[7];
    tree[5].right = NULL;
    tree[5].next = &tree[2];

    tree[6].val = 9;
    tree[6].left = NULL;
    tree[6].right = NULL;
    tree[6].next = &tree[3];

    tree[7].val = 6;
    tree[7].left = &tree[8];
    tree[7].right = &tree[9];
    tree[7].next = &tree[5];

    tree[8].val = 8;
    tree[8].left = NULL;
    tree[8].right = NULL;
    tree[8].next = &tree[7];

    tree[9].val = 1;
    tree[9].left = NULL;
    tree[9].right = NULL;
    tree[9].next = &tree[7];

    cout << solu.GetNext(&tree[7])->val << endl;
    return 0;
}