题解39 | 具有误导性的next指针#二叉树的下一个结点#

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
#include <cstddef>//nullptr
/*"#include <cstddef>" 是一个C++标准库头文件，用于包含一些与指针和内存相关的类型和函数。
"cstddef" 是 "C Standard Definitions" 的缩写，意为C标准定义。它定义了一些与C语言兼容的常用宏和类型，这些宏和类型通常在C++中使用。
这个头文件中包含的一些常用类型有：
- size_t：用于表示对象的大小或数组的长度的无符号整数类型。
- ptrdiff_t：用于表示指针之间的差值的有符号整数类型。
- nullptr_t：表示空指针常量的特殊类型。
- max_align_t：表示对象的最大对齐要求的类型。
此外，该头文件还定义了一些与指针和内存相关的函数，如：
- offsetof：用于获取结构体成员的偏移量。
- alignof：用于获取类型的对齐要求。
通过包含这个头文件，可以在C++程序中使用这些类型和函数，以方便地进行指针和内存操作。*/
#include <vector>
class Solution {
public:
    vector<TreeLinkNode*> res;
    void dfs(TreeLinkNode *root){
        if(root == NULL) return ;

        dfs(root->left);
        res.push_back(root);
        dfs(root->right);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode *root = pNode;
        //注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
        //传入的是子树根，我们要先找着总根
        //不过我觉得叫pre指针更好，叫next有误导性
        while (root->next) {
            root = root->next;
        }

        dfs(root);

        int n = res.size();

        for (int i = 0; i < n; i++) {
            TreeLinkNode *now = res[i];
            if(pNode == now){
                return res[i+1];
            }
        }

        return NULL;
    }
};

基本算法思想

通过深度优先搜索（DFS）遍历整个树，将遍历的结果存储在一个vector中。然后在vector中找到给定节点的下一个节点。

具体步骤如下：

1. 定义一个vector<TreeLinkNode*> res，用于存储遍历的结果。

2. 实现一个递归的深度优先搜索函数dfs，遍历树的过程中将每个节点存入res中。

3. 在GetNext函数中，先找到整个树的根节点，即通过不断向上遍历节点的next指针，直到找到最顶层的根节点。

4. 调用dfs函数对整个树进行遍历，将遍历结果存入res中。

5. 获取res的大小n，遍历res，找到给定节点pNode在res中的位置i，返回res[i+1]作为给定节点的下一个节点。

时间复杂度：

- 遍历整个树的时间复杂度为O(N)，其中N是树中节点的数量。

- 获取给定节点的下一个节点的时间复杂度为O(N)，需要遍历res找到给定节点的位置。

空间复杂度：

- 使用了一个额外的vector<TreeLinkNode*> res，存储了整个树的遍历结果，所以空间复杂度为O(N)，其中N是树中节点的数量。