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

/*
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 midVis(TreeLinkNode* pNode)
{
if(!pNode->left)
{
return pNode;
}

    return midVis(pNode->left);
}

TreeLinkNode* findParent(TreeLinkNode* pNode)
{
    TreeLinkNode* parent=pNode->next;

    if(!parent)
    {
        return NULL;
    }

    if(parent->left == pNode)
    {
        return parent;
    }
    else if(parent->right == pNode)
    {
        return findParent(parent);
    }

    return NULL;
}

TreeLinkNode* GetNext(TreeLinkNode* pNode) {
    if(!pNode  ) //为空，直接返回null
    {
        return NULL;
    }
    if(!pNode->right)//没有右子树，需要向上寻找 第一个身为左孩子的结点 的双亲结点
    {
        return findParent(pNode);
    }
    return midVis(pNode->right);//有右子树，向它的右子树寻找最左结点。
}

};