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

/*
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){//当前节点有右子树时
            TreeLinkNode* mostLeft=pNode->right;
            while(mostLeft->left){//一直往左下走
                mostLeft=mostLeft->left;
            }
            return mostLeft;
        }
        else{//说明当前节点没有右子树
            //此时往上找节点是其父节点的左孩子的节点，这个节点的父节点就是要找的节点
            TreeLinkNode* parent=pNode->next;//父节点
            while(parent&&parent->right==pNode){
                pNode=parent;
                parent=parent->next;//往上继续找
            }
            if(parent){
                return parent;
            }
            else{
                return NULL;
            }
        }
        return NULL;
    }
    
};