1028. Recover a Tree From Preorder Traversal¶
题目信息¶
- 题号:
1028
- 难度:
Hard
- 主题:
二叉树、深度编码、先序恢复
- 原题:
- 重点:
每个节点值前的横线数量等于节点深度;节点按先序出现,若某节点只有一个孩子则该孩子保证为左孩子
题目重述¶
给定字符串 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 的根节点。