1028. Recover a Tree From Preorder Traversal

题目信息

题号:

1028

难度:

Hard

主题:

二叉树、深度编码、先序恢复

原题:

LeetCode 1028

重点:

每个节点值前的横线数量等于节点深度;节点按先序出现,若某节点只有一个孩子则该孩子保证为左孩子

题目重述

给定字符串 traversal,它编码了一棵二叉树的先序遍历。根节点深度为 0;深度为 d 的节点在十进制节点值之前恰好带有 d 个连续横线 -。节点按照“根、左子树、右子树”的顺序写入。

根据这个字符串恢复并返回原二叉树。节点值为正整数,可能包含多位数字。若某节点在原树中只有一个子节点,题目保证该节点是左孩子,因此编码能够唯一恢复树结构。

树中节点数在 [1, 1000] 范围内,1 <= Node.val <= 10^9。

自建示例

相同深度的节点依次属于左右子树:

输入:traversal = "1-2--4--5-3--6"
输出:[1,2,3,4,5,6]
解释:1 的深度为 0;2 和 3 的深度为 1;4、5 是 2 的两个孩子,6 是 3 的左孩子。

编码中只有根节点:

输入:traversal = "42"
输出:[42]
解释:字符串中没有横线和后续节点,因此恢复出的树只有值为 42 的根节点。