题解 | #二叉树的下一个结点#

/*
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) return NULL;

        //如果当前结点的右子树是不为空
        if(pNode->right){
            pNode = pNode->right;
            while(pNode->left){//因为我要最左边的节点，而不是这个空节点，所以我只需要pNode->left 为空为止。
                pNode = pNode->left;//向左走
            }

            return pNode;
        }

         //当前结点无右子树时，判断结点是父结点的左子树还是右子树
        while(pNode->next){

            if(pNode==pNode->next->left){
                return pNode->next;
            }

            pNode = pNode->next;

        }

        return NULL;




    }
};