1028：从先序遍历还原二叉树（1797 分）

力扣第 132 场周赛第 4 题

题目

我们从二叉树的根节点 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
  • 显然当前节点即为上个节点的子节点，应该接到上个节点的下面
  • 如果上个节点还没有左子树，就接到左边，否则接到右边
• 否则，去掉上个节点直到找到深度比当前节点深度大 1 的节点，转为上一步

这个过程显然可以用栈。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
	stack = []
	for w,x in re.findall('(\-*)(\d+)', traversal):
		w,x = len(w),TreeNode(int(x))
		while stack and stack[-1][1]!=w-1:
			stack.pop()
		if stack:
			y = stack[-1][0]
			if not y.left:
				y.left = x
			else:
				y.right = x
		stack.append((x,w))
	return stack[0][0]

40 ms