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

此题考查的是有关于中序遍历的基础知识-中序遍历的下一个节点。
做题思路写在了注释里面。
直接上代码⬇️

#include <iostream>
using namespace std;
struct TreeLinkNode {
    int val;
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next; // 指向父节点的指针
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
/**
 * 如果一个节点有右子树，那么返回右子树最左节点
 * 如果节点是它父亲节点的左节点，那么返回他的父节点
 * 如果节点是它父亲的右节点，且它没有右子树，那么沿着父节点的指针向上遍历，直到找到是它父节点的左节点的节点，返回其父节点，若没有，则返回nullptr
 * @param pNode 指定节点
 * @return pNext pNode下一个中序遍历序列的节点指针
 */
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
    if (pNode == nullptr)
        return nullptr;
    TreeLinkNode *pNext = nullptr;
    if (pNode->right != nullptr) { // 有右子树
        pNext = pNode->right;
        while (pNext->left != nullptr)
            pNext = pNext->left;
    } else { // 无右子树
        TreeLinkNode *pParent = pNode->next;
        if (pParent != nullptr && pParent->left == pNode) // 是其父节点的左节点
            pNext = pParent;
        else { // 是其父节点的右节点
            TreeLinkNode *pCurrent = pNode;
            while (pParent != nullptr && pCurrent == pParent->right) {
                pCurrent = pParent;
                pParent = pCurrent->next;
            }
            pNext = pParent;
        }
    }
    return pNext;
}
int main() {
    TreeLinkNode *n1 = new TreeLinkNode(1);
    TreeLinkNode *n2 = new TreeLinkNode(2);
    TreeLinkNode *n3 = new TreeLinkNode(3);
    TreeLinkNode *n4 = new TreeLinkNode(4);
    TreeLinkNode *n5 = new TreeLinkNode(5);
    TreeLinkNode *n6 = new TreeLinkNode(6);
    TreeLinkNode *n7 = new TreeLinkNode(7);
    TreeLinkNode *n8 = new TreeLinkNode(8);
    TreeLinkNode *n9 = new TreeLinkNode(9);
    n1->left = n2;
    n1->right = n3;
    n2->next = n1;
    n2->left = n4;
    n2->right = n5;
    n3->next = n1;
    n3->left = n6;
    n3->right = n7;
    n4->next = n2;
    n5->next = n2;
    n5->left = n8;
    n5->right = n9;
    n6->next = n3;
    n7->next = n3;
    n8->next = n5;
    n9->next = n5;
    cout << GetNext(n1)->val << endl << GetNext(n4)->val << endl << GetNext(n9)->val << endl;
    if (!GetNext(n7)) cout << "nullptr" << endl;
    return 0;
}