1028. 从先序遍历还原二叉树 [hard]

1028. 从先序遍历还原二叉树 [hard]

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

我们从二叉树的根节点 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 之间。

通过次数15,601 | 提交次数21,100

First Try

2020-06-26

本来还打算用一些深度遍历的方式把节点放进去，但是只能保证层级，无法跟踪到正确的父节点。仔细观察字符串，发现每个节点前面肯定有其父节点，而且第一个比它等级高的点肯定就是其父节点，观察到这一点问题游刃而解。剩下的就是之前没有考虑到的一个元素有不同字符长度的可能了，导致了一个错误提交。

看了一眼题解，按照深度遍历时候栈的使用方式来模拟，这是我没有想过的方式，尤其是切换到右节点的思路有点特别。很多时候用自己的方法写出来还比较快，想去了解下官方题解反而要花去大半个小时。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def recoverFromPreorder(self, S):
        """
        :type S: str
        :rtype: TreeNode
        """
        if not S:
            return TreeNode(None)

        # root = TreeNode(S[0])
        # root.level = 0
        node_collection = []
        i = 0
        l = 0
        val = ""
        while i < len(S):
            if S[i] == "-":
                l += 1
                i += 1
            else:
                while i <len(S) and S[i] != "-":
                    val += S[i]
                    i += 1 
                node = TreeNode(val)
                node.level = l
                if not node_collection:  # root
                    node_collection.append(node)
                else:
                    for n in reversed(node_collection):
                        if n.level < node.level:
                            if not n.left:
                                n.left = node
                            elif not n.right:
                                n.right = node
                            node_collection.append(node)
                            break
                l = 0
                val = ""
        return node_collection[0]

• 执行用时：88 ms, 在所有 Python 提交中击败了48.97%的用户
• 内存消耗：13.8 MB, 在所有 Python 提交中击败了100.00%

Bug Version

使用回溯递归写的版本，本来觉得一切顺利，后来测试才发现无法准确跟踪到父节点，只能准确判断层级。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def recoverFromPreorder(self, S):
        """
        :type S: str
        :rtype: TreeNode
        """
        if not S:
            return []
        root = TreeNode(S[0])
        root.lev = 0

        # place value via DSF recursion, level mark is crucial
        def place(lev, val,node):
            if node.lev == lev:
                if node.val is None:
                    node.val = val
                    return True
                else:
                    return False
            if node.lev < lev:
                if not node.left:
                    node.left = TreeNode(None)
                    node.left.lev = node.lev + 1  # should be set
                if not node.right:
                    node.right = TreeNode(None)
                    node.right.lev = node.lev + 1
                rv = place(lev, val, node.left)
                if not rv:
                    rv = place(lev, val, node.right)
                return rv
            return False  # error in fact

        level_col = [[S[0]]]
        def consume(st, node):
            lev = 0
            while st[lev] == "-":
                lev += 1
            val = st[lev]
            if len(level_col) < lev + 1:
                level_col.append([])
            level_col[lev].append(val)
            # key point, place val in correct position
            place(lev, val, node)
            if len(st) > lev + 1:
                consume(st[lev + 1:], node)

        consume(S[1:], root)
        print(root)
        return root