1028. Recover a Tree From Preorder Traversal ============================================ 题目信息 -------- :题号: 1028 :难度: Hard :主题: 二叉树、深度编码、先序恢复 :原题: `LeetCode 1028 `_ :重点: 每个节点值前的横线数量等于节点深度;节点按先序出现,若某节点只有一个孩子则该孩子保证为左孩子 题目重述 -------- 给定字符串 ``traversal``,它编码了一棵二叉树的先序遍历。根节点深度为 ``0``;深度为 ``d`` 的节点在十进制节点值之前恰好带有 ``d`` 个连续横线 ``-``。节点按照“根、左子树、右子树”的顺序写入。 根据这个字符串恢复并返回原二叉树。节点值为正整数,可能包含多位数字。若某节点在原树中只有一个子节点,题目保证该节点是左孩子,因此编码能够唯一恢复树结构。 树中节点数在 ``[1, 1000]`` 范围内,``1 <= Node.val <= 10^9``。 自建示例 -------- 相同深度的节点依次属于左右子树: .. code-block:: text 输入:traversal = "1-2--4--5-3--6" 输出:[1,2,3,4,5,6] 解释:1 的深度为 0;2 和 3 的深度为 1;4、5 是 2 的两个孩子,6 是 3 的左孩子。 编码中只有根节点: .. code-block:: text 输入:traversal = "42" 输出:[42] 解释:字符串中没有横线和后续节点,因此恢复出的树只有值为 42 的根节点。