Skip to main content

3-29 1028. 从先序遍历还原二叉树

Date:2022-03-29 08:47:44

题目:1028. 从先序遍历还原二叉树 ( 困难😟 )

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,则其直接子节点的深度为 D + 1。根节点的深度为 0)。

如果节点只有一个子节点,那么保证该子节点为左子节点。

给出遍历输出 S,还原树并返回其根节点 root

示例

示例 1:

img

输入:"1-2--3--4-5--6--7"
输出:[1,2,5,3,4,6,7]

示例 2:

img

输入:"1-2--3---4-5--6---7"
输出:[1,2,5,3,null,6,null,4,null,7]

分析

  • 迭代+单调栈

    image-20220329215318913

    有三个要点:

    • 尝试获取 level
    • 尝试获取 val
    • 根据 level 与栈高度,尝试挂载 node
      • 如果 level 与栈高度相等,挂载为 左节点 即可
      • 如果 level 小于栈高度,先出栈,直到 level 与栈高度相等,挂载为 右节点 即可

题解

迭代+单调栈

import { TreeNode111, TreeNode } from './common/utils'

function recoverFromPreorder(traversal: string): TreeNode | null {
const len = traversal.length
let pos = 0
const stack: TreeNode[] = []
while (pos < len) {
let level = 0
while (pos < len && traversal.charAt(pos) == '-') {
pos++
level++
}

let val = 0
while (pos < len && traversal.charAt(pos) != '-') {
val = 10 * val + Number(traversal.charAt(pos))

pos++
}

console.log('[val, pos and stack]:', val, pos)
const newNode = new TreeNode(val)
if (level == stack.length) {
if (stack[stack.length - 1]) {
stack[stack.length - 1].left = newNode
}
} else if (level < stack.length) {
while (level != stack.length) {
stack.pop()
}

stack[stack.length - 1].right = newNode
}

stack.push(newNode)
}

return stack[0] ?? null
}

使用

function main() {
const traversal = '1-2--3--4-5--6--7'

console.log('[]:', recoverFromPreorder(traversal))
}

main()

export {}