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

1 问题

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

2 分析

比如我现在的二叉树如下

                4
           2         6
        1     3   5     7 

这里分3种情况

1) 如果这个节点包含右子树，那么下一个节点就是这个右子树的最左下节点，比如节点4的下一个节点是5.

2) 如果这个节点不包含右子树，如果这个节点的父节点的左子节点是同一个，那么下一个节点就是这个节点的父节点，比如节点6的下一个节点就是7.

3) 如果这个节点不包含右子树，如果这个节点的父节点的右子节点是同一个，这里分2种情况，我们先找到这节点的父结点，然后父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点，比如节点3的下一个节点是4，也有可能没有下一个节点，比如节点7的下一个节点就是空。

3 代码实现

typedef struct Tree
{
    int value;
    struct Tree* left;
    struct Tree* right;
    struct Tree* parent;
    Tree(int value) : value(value), left(NULL), right(NULL), parent(NULL) {}
    Tree() : value(0), left(NULL), right(NULL), parent(NULL) {}
} Tree;

Tree* getNext(Tree* node)
{
    if (NULL == node)
        return NULL;
    Tree* nextNode = NULL;
    if (NULL != node->right)
    {
        Tree* rightNode = node->right;
        while (rightNode->left != NULL)
        {
            rightNode = rightNode->left;
        }
        nextNode = rightNode;
    }
    else
    {
        Tree* currentNode = node;
        Tree* parentNode = currentNode->parent;
        while (NULL != parentNode && parentNode->right == currentNode)
        {
            currentNode = parentNode;
            parentNode = currentNode->parent;
        }
        nextNode = parentNode;
    }
    return nextNode;
}