1028_从先序遍历还原二叉树

难度：困难

题目

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

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

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

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

示例

示例一：

img

输入：”1-2–3–4-5–6–7”
输出：[1,2,5,3,4,6,7]

示例二：

img

输入：”1-2–3—4-5–6—7”
输出：[1,2,5,3,null,6,null,4,null,7]

示例三：

img

输入：”1-401–349—90–88”
输出：[1,401,null,349,88,90]

提示

  • 原始树中的节点数介于 1 和 1000 之间。
  • 每个节点的值介于 1 和 10 ^ 9 之间。

解题

基本思路是按照先序遍历的顺序创建二叉树，每次都判断深度，当深度不一致时，就回溯

寻找连续的 - 和连续数字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int val = 0, nextlevel=0,index;
  TreeNode node = null;
	// 从 start 开始遍历字符串
  for(index = start; index<traversal.length();index++){
    // 遇到 - ，则 nextlevel增加1
    if(traversal.charAt(index)=='-') {
      nextlevel++;
    } else{
      // 遇到字符则将值存储起来
      while(index<traversal.length() && traversal.charAt(index)!='-'){
        val = val*10+traversal.charAt(index)-'0';
        index++;
      }
      break;
    }
  }

当当前 level 等于 nextlevel 时，说明此时处理的内容为本层节点

1
2
3
4
5
6
7
8
if(level == nextlevel){
    node = new TreeNode();
    node.val = val;
    start = index;
  // 先左后右
    node.left = dfs(level+1, traversal);
    node.right = dfs(level+1, traversal);
  }

组合起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 记录当前访问到字符串的位置
int start = 0;
public TreeNode recoverFromPreorder(String traversal) {
  return dfs(0,traversal);
}
public TreeNode dfs(int level, String traversal){
  int val = 0, nextlevel=0,index;
  TreeNode node = null;
  for(index = start; index<traversal.length();index++){
    if(traversal.charAt(index)=='-') {
      nextlevel++;
    } else{
      while(index<traversal.length() && traversal.charAt(index)!='-'){
        val = val*10+traversal.charAt(index)-'0';
        index++;
      }
      break;
    }
  }
  // 与当前深度不一致时，回溯
  if(level == nextlevel){
    node = new TreeNode();
    node.val = val;
    start = index;
    node.left = dfs(level+1, traversal);
    node.right = dfs(level+1, traversal);
  }
  return node;
}