CodingInterview-二叉树的下一个结点

这道题判断起来比较麻烦，需要分为几种情况进行讨论。

首先我考虑的是根据是否是叶子节点。如果是非叶子节点，那么下一个节点就是右子树中序遍历的第一个节点（也就是该节点右孩子的最底层左孩子，如果右孩子是叶子节点，那么就是右孩子）。如果是叶子节点，也要分为两种情况讨论，如果有父亲节点，且是父节点的左子树，那么下一个节点就是父节点；如果是父节点的右子树，那么下一个节点就需要递归父节点，直到某父节点是其父节点的左孩子。

在看完书以后，我发现这几种情况还可以再做抽象，首先如果一个节点有右子树，那么就可以根据非叶子节点的情况去考虑；如果一个节点没有右子树，那么就需要考虑它的父节点，然后再分为该节点是父节点的左孩子还是右孩子去讨论。讨论的结果和上面基本相同。

在编码时还需要注意判断需要查看的节点是否为空，如果未空，那就说明判断失败，直接返回 NULL 即可。

/*
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;
        if(pNode->right!=NULL){
            TreeLinkNode* next=pNode->right;
            while(next->left!=NULL) next=next->left;
            return next;
        }else{
            if(pNode->next!=NULL){
                if(pNode==pNode->next->left){
                    return pNode->next;
                }else{
                    TreeLinkNode* parent=pNode->next;
                    while(parent->next!=NULL){
                        if(parent==parent->next->left) return parent->next;
                        parent=parent->next;
                    }
                }
            }
        }
        return NULL;
    }
};