# 1028. Recover a Tree From Preorder Traversal

Reference: LeetCode

Difficulty: Hard

## Problem

We run a preorder depth first search on the

`root`

of a binary tree.

At each node in this traversal, we output

`D`

dashes (where`D`

is the depth of this node), then we output the value of this node. (If the depth of a node is`D`

, the depth of its immediate child is`D + 1`

. The depth of the root node is`0`

.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output

`S`

of this traversal, recover the tree and return its root.

**Example:**

1 | Input: "1-2--3--4-5--6--7" |

1 | Input: "1-2--3---4-5--6---7" |

## Analysis

**Methods:**

- Recursion
- Do an iterative depth first search, parsing dashes from the string to know how to link the nodes together.
- Be careful of the corner cases.
- The value may consist of several digits.
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

30

31

32

33

34

35

36

37

38

39private int index = 0;

public TreeNode recoverFromPreorder(String s) {

index = 0;

return construct(s, 0);

}

// 1-2--3--4-5--6--7

//

private TreeNode construct(String s, int depth) {

// parse dash

int numDash = 0;

// index is pointing to the first "-"

// E.g. root = 1, in this case, numDash is 0

while (index + numDash < s.length() && s.charAt(index + numDash) == '-') {

numDash += 1;

}

// base case

if (numDash != depth) { // go back (backtracking)

return null;

}

int valLength = 0; // index + numDash is pointing to the first digit

while (index + numDash + valLength < s.length() && s.charAt(index + numDash + valLength) != '-') {

valLength += 1;

}

String subStr = s.substring(index + numDash, index + numDash + valLength); // [x, x + len)

int rootVal = Integer.parseInt(subStr);

TreeNode root = new TreeNode(rootVal);

index += numDash + valLength; // update index

root.left = construct(s, depth + 1);

root.right = construct(s, depth + 1);

return root;

}

**Time:** $O(S)$ where $S$ is the length of the string.

**Space:** $O(h)$

Comment