题目描述
我们从二叉树的根节点 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 之间。
算法1
(递归) $O(nlogn)$
先将字符串转化为一个list，list中每个元素为一个元组，元组第一项为结点深度，第二项为结点值。以样例1为例，因为先序遍历第一个肯定为根结点，所以根结点不用转换，直接构造即可，其余结点按字符串”1-2–3–4-5–6–7”转化结果为[(1, 2), (2, 3), (2, 4), (1, 5), (2, 6), (2, 7)]。然后我们需要在剩余结点中找到深度为1的两个结点（如果只有一个，那么就作为左子结点），将找到的两个子结点连接到父结点上，然后将所有结点深度减一（或者将搜索深度加一），递归寻找子结点。直到list为空即可。
时间复杂度分析：搜索深度为logn，每次搜索都遍历所有子结点n，总时间复杂度为$O(nlogn)$
Python3 代码
# 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
"""
i = 0
while i < len(S) and S[i] != '-':
i += 1
root = TreeNode(int(S[:i]))
nodes = []
while i < len(S):
cnt = 0
while i < len(S) and S[i] == '-':
i += 1
cnt += 1
j = i
while j < len(S) and S[j] != '-':
j += 1
nodes.append((cnt, int(S[i:j])))
i = j
# print(nodes)
def helper(root, nodes):
if not nodes:
return
left = None
right = None
index = -1
for i in range(len(nodes)):
if nodes[i][0] == 1:
if left == None:
left = TreeNode(nodes[i][1])
else:
right = TreeNode(nodes[i][1])
index = i
nodes[i] = (nodes[i][0] - 1, nodes[i][1])
root.left = left
root.right = right
if index > -1:
helper(root.left, nodes[1:index])
helper(root.right, nodes[index + 1:])
else:
helper(root.left, nodes[1:])
helper(root, nodes)
return root
