1028.Recover a Tree From Preorder Traversal

Tags: Hard Tree Depth-first Search

Links: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

---

We run a preorder depth first search on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output S of this traversal, recover the tree and return its root.

Example 1:

Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Note:

• The number of nodes in the original tree is between 1 and 1000.
• Each node will have a value between 1 and 10^9.

---

构建二叉树一般采用递归的方法去构建，和LeetCode 297.二叉树的序列化与反序列化思路上有共同点，可以认为本题是二叉树序列化的一种方式，现在题目给出了序列化的结果，我们需要进行反序列化的操作。

用一个全局变量pos记录读取到字符串s中的位置，构建根节点时，用end指向pos后面的第一个-字符，或者指向字符串末尾，构建完根节点，pos移动到根节点数字的最后一个数字，比如说根节点数字为401，最开始pos指向4，构建完根节点后pos指向1。

然后构建左右子树，用cnt去记录-字符的数量，参数depth代表上一层的深度，如果cnt = depth + 1，那么意味着一定存在左子节点（题目保证如果节点只有一个子节点，一定是左子节点），所以此时需要移动pos的位置，让其继续指向数字。如果cnt != depth + 1，那么意味着根节点的左子节点不存在。

然后构建右子节点，这时候pos的位置可能更新了，也可能并没有变化，所以仍然需要继续用end指向pos后面的第一个-字符，或者指向字符串末尾，继续用cnt去记录-的数量，完成右子树的构建。

只需要遍历依次字符串s即可完成构建，时间复杂度$O(n)$。

最开始写了一个版本，写完后发现构建左右子树的代码其实是一样的，可以进一步进行优化：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int pos;
public:
    TreeNode* recoverFromPreorder(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (s.size() == 0) return NULL;

        pos = 0;
        TreeNode *root = build(s, 0);
        return root;
    }

    TreeNode *build(const string & s, int depth)
    {
        int end = (s.find("-", pos) == string::npos) ? (int)s.size() : s.find("-", pos);
        TreeNode *root = new TreeNode(stoi(s.substr(pos, end - pos)));
        pos += end - pos - 1;
        int cnt = 0;
        for (int i = end; i < s.size(); ++i) {
            if (s[i] == '-') ++cnt;
            else break;
        }

        pos += (cnt == depth + 1) ? cnt + 1 : 0;
        root -> left = (cnt == depth + 1) ? build(s, depth + 1) : NULL;

        end = (s.find("-", pos) == string::npos) ? (int)s.size() : s.find("-", pos);
        cnt = 0;
        for (int i = end; i < s.size(); ++i) {
            if (s[i] == '-') ++cnt;
            else break;
        }
        pos += (cnt == depth + 1) ? cnt + 1 : 0;
        root -> right = (cnt == depth + 1) ? build(s, depth + 1) : NULL;

        return root;
    }
};

优化的递归版本，此时让pos每次指向数字后的第一个-，用cnt去记录-的个数，优先计算-，代表马上要建立的节点的深度，depth代表当前层的深度，如果cnt != depth，意味着接下来的数字并不属于这一层，所以直接返回即可。

如果相等，那么让pos移动cnt个位置，指向-后的第一个数字，然后用end指向数字后的-，提取出数字，构建根节点，此时pos移动到end的位置，于是pos又指向了数字后的第一个-，于是就可以递归的去构建左右子树了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int pos;
public:
    TreeNode* recoverFromPreorder(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (s.size() == 0) return NULL;

        pos = 0;
        TreeNode *root;
        build(s, root, 0);
        return root;
    }


    void build(const string & s, TreeNode *&root, int depth)
    {
        int cnt = 0;
        for (int i = pos; i < s.size(); ++i) {
            if (s[i] == '-') ++cnt;
            else break;
        }

        if (cnt != depth) { root = NULL; return; }

        pos += cnt;
        int end = (s.find("-", pos) == string::npos) ? (int)s.size() : s.find("-", pos);
        root = new TreeNode(stoi(s.substr(pos, end - pos)));
        pos += end - pos;

        build(s, root -> left, depth + 1);
        build(s, root -> right, depth + 1);
    }
};