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

Ian

2019-04-14 约 578 字预计阅读 2 分钟次阅读

力扣第 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
15
16


class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        sk = []
        for h,x in re.findall('(-*)(\d+)',traversal):
            h,x = len(h),int(x)
            u = TreeNode(x)
            while sk and sk[-1][0]>=h:
                sk.pop()
            if sk:
                fa = sk[-1][1]
                if fa.left:
                    fa.right = u
                else:
                    fa.left = u
            sk.append((h,u))
        return sk[0][1]

4 ms

目录

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

题目

分析

解答