【9.1】树结构-从先序遍历还原二叉树

一、题目

        我们从二叉树的根节点 root 开始进行深度优先搜索。

        在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

        如果节点只有一个子节点，那么保证该子节点为左子节点。

        给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

提示：

• 原始树中的节点数介于 1 和 1000 之间。
• 每个节点的值介于 1 和 10 ^ 9 之间。

二、解题思路

2.1 迭代思路

        这道题的输入是一个二叉树的前序遍历结果，但仅凭前序遍历结果是无法唯一确定一棵二叉树的。不过，题目还提供了两个额外的条件：一是每个数字前面的“-”表示当前节点的深度，二是如果一个节点只有一个子节点，那么这个子节点必须是左子节点。有了这两个条件，我们就可以唯一地还原出这棵二叉树。

        接下来，我们来看一下具体的解题思路：

        首先，我们可以使用一个栈来辅助构建二叉树。我们将创建的节点依次压入栈中。通过观察可以发现，从栈底到栈顶，每两个相邻的节点之间都是父子关系。为了更好地理解这个过程，我们可以画一个图来辅助分析。当我们把左边节点1，2，3压入栈之后

        通过上图我们可以观察到，从栈底到栈顶，节点1是节点2的父节点，节点2又是节点3的父节点。此外，还有一个关键点：栈中元素的个数减去1，就是栈顶元素的深度。这个特性非常重要。之所以要减1，是因为树中节点的深度是从0开始计算的，而不是从1开始，根节点的深度为0。

        在创建每个节点时，我们需要先找到它的父节点，然后将当前节点挂到父节点下面。那么如何找到父节点呢？我们可以通过栈中元素的个数来确定。看到这里，相信大家已经能够写出代码了。下面我们分步骤来说明：

1. **确定当前节点的深度**  
        通过输入中的“-”数量，我们可以直接得到当前节点的深度。

2. **提取当前节点的值**  
        从输入中提取出节点的值，用于创建当前节点。

3. **找到当前节点的父节点**  
        根据前面的分析，栈中元素的个数减去1就是栈顶节点的深度。我们可以通过循环判断，当栈中元素的个数等于当前节点的深度时，栈顶元素就是当前节点的父节点。

4. **将当前节点挂到父节点下面**  
        根据题目的条件，如果一个节点只有一个子节点，那么这个子节点必须是左子节点。因此，我们需要根据父节点的子节点情况，将当前节点挂到左子节点或右子节点的位置。需要注意的是，根节点没有父节点，需要单独处理。

        通过以上步骤，我们就可以逐步构建出完整的二叉树。

#include <stack>
#include <string>

using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* recoverFromPreorder(string S) {
    stack<TreeNode*> stack;
    int i = 0;
    while (i < S.length()) {
        // 找出当前数字的深度，从0开始的，根节点是第0层
        int level = 0;
        while (i < S.length() && S[i] == '-') {
            level++;
            i++;
        }
        // 找出当前节点的值
        int val = 0;
        while (i < S.length() && S[i] != '-') {
            val = val * 10 + (S[i] - '0');
            i++;
        }
        // 找到当前节点的父节点，子节点的深度要比父节点大1
        while (stack.size() > level) {
            stack.pop();
        }
        // 创建当前节点
        TreeNode* node = new TreeNode(val);
        // 栈为空说明当前节点是根节点，如果栈不为空，说明
        // 当前节点不是根节点，需要把当前节点挂到父节点下面
        if (!stack.empty()) {
            // 如果节点只有一个子节点，那么保证该子节点为左子节点
            if (stack.top()->left == nullptr) {
                stack.top()->left = node;
            } else {
                // 如果左子节点不为空，就放到右子节点中
                stack.top()->right = node;
            }
        }
        // 把当前节点压入栈
        stack.push(node);
    }
    // 除了根节点，其他子节点全部出栈
    while (stack.size() > 1) {
        stack.pop();
    }
    // 返回根节点
    return stack.empty() ? nullptr : stack.top();
}


int main() {
    string S = "1-2--3--4-5--6--7";
    TreeNode* root = recoverFromPreorder(S);
    // 这里可以添加遍历二叉树的代码来验证结果
    return 0;
}

2.2 拆开字符串

        题目中提到，节点是通过分隔符 `-` 隔开的，因此我们可以按照 `-` 将字符串拆分成多个部分。这里我们不需要使用栈，而是可以使用一个列表（`list`）来存储每一层的节点。需要注意的是，每一层只存储一个节点。

        这里可能会让人产生疑问：每一层有那么多节点，为什么只存储一个？会不会覆盖掉之前的节点？实际上，覆盖是没问题的。如果某个节点被覆盖了，说明这个节点以及它的所有子节点、孙子节点等都已经完全访问过了，后续不会再需要访问它们。

        举个例子，假设在下图中，红色的节点 `3` 位于第二层。当遍历到节点 `3` 时，它会覆盖掉第二层之前存储的节点 `2`。虽然节点 `2` 被覆盖了，但这并不会影响结果，因为节点 `2` 及其所有子节点都已经被访问完毕，后续不会再需要用到它们。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 还原二叉树的函数
TreeNode* recoverFromPreorder(string S) {
    // 通过 "-" 分隔符把字符串拆开
    vector<string> nodeValues;
    stringstream ss(S);
    string item;
    while (getline(ss, item, '-')) {
        nodeValues.push_back(item);
    }

    // 使用一个列表存储每层的节点
    vector<TreeNode*> list;
    // 数组中的第一个值肯定是根节点，创建根节点并添加到 list 中
    list.push_back(new TreeNode(stoi(nodeValues[0])));

    // 上面根节点已经加入到 list 中了，下面都是非根节点
    int level = 1;
    for (int i = 1; i < nodeValues.size(); i++) {
        if (!nodeValues[i].empty()) {
            TreeNode* node = new TreeNode(stoi(nodeValues[i]));
            // 因为是前序遍历，每层我们只需要存储一个节点即可
            // 这个节点值有可能会被覆盖，如果被覆盖了说明这个节点及其子节点都已经遍历过了
            if (list.size() > level) {
                list[level] = node;
            } else {
                list.push_back(node);
            }

            // 获取父节点
            TreeNode* parent = list[level - 1];
            // 左子节点为空，优先添加到左子节点中
            if (parent->left == nullptr) {
                parent->left = node;
            } else {
                parent->right = node;
            }

            // 深度重新赋值
            level = 1;
        } else {
            // 统计节点的深度
            level++;
        }
    }

    // 返回树的根节点
    return list[0];
}

// 辅助函数：打印二叉树的前序遍历结果
void printTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

// main 函数用于测试
int main() {
    string S = "1-2--3--4-5--6--7";
    TreeNode* root = recoverFromPreorder(S);

    // 打印还原后的二叉树前序遍历结果
    cout << "还原后的二叉树前序遍历结果: ";
    printTree(root);
    cout << endl;

    return 0;
}