lc1028-从先序遍历还原二叉树

题目描述

• 字符串转二叉树
• 根节点深度为 0，其子节点深度为 1，依次类推
• 题目保证若只有一个子节点，必为左子树

示例

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]
解释：1/   \2     5/ \   / \
3   4 6   7

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]
解释：1/  \2    5/    /3    6/    /
4    7

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]
解释：1/401/   \349    88/
90

题解

• 思路：递归
  1. 把字符串按顺序解析出来，记录信息对：(深度, 值)
  2. 若下一个节点的深度比当前节点大，说明是儿子节点，继续 dfs；不然就回溯

type Node struct {depth intval   int
}var nodes = make([]Node, 0, 1010)
var k = 0func recoverFromPreorder(traversal string) *TreeNode {n := len(traversal)for i := 0; i < n; {depth, val := 0, 0for traversal[i] == '-' {depth ++i ++}for i < n && traversal[i] != '-' {val = val * 10 + int(traversal[i] - '0')i ++}nodes = append(nodes, Node{depth, val})}return dfs(0)
}func dfs(d int) *TreeNode {if k == len(nodes) { return nil }root := &TreeNode{Val: nodes[k].val}k ++if k < len(nodes) && d < nodes[k].depth {root.Left = dfs(d + 1)}if k < len(nodes) && d < nodes[k].depth {root.Right = dfs(d + 1)}return root
}