1028. Recover a Tree From Preorder Traversal #

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"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Note:

• The number of nodes in the original tree is between 1 and 1000.
• Each node will have a value between 1 and 10^9.

Problem Summary #

We perform a depth-first search starting from the root node root of the binary tree.

At each node in the traversal, we output D dashes (where D is the depth of the node), then output the value of the node. (If the depth of a node is D, then 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 traversal output S, restore the tree and return its root node root.

Constraints:

• The number of nodes in the original tree is between 1 and 1000.
• Each node’s value is between 1 and 10 ^ 9.

Solution Ideas #

• Given a string, which is the result of a preorder traversal of a tree, where the number of dashes represents the level. Generate the corresponding tree according to this string.
• The idea for this problem is relatively clear: use DFS to solve it. While doing a depth-first scan of the string, determine whether the current node belongs to this level based on the number of dashes. If it does not belong to this level, backtrack to the previous root node, add the leaf node, and then continue the depth-first search. Note that during each DFS, the index used to scan the string must be preserved throughout, and this index is also needed during backtracking.

Code #

package leetcode

import (
	"strconv"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverFromPreorder(S string) *TreeNode {
	if len(S) == 0 {
		return &TreeNode{}
	}
	root, index, level := &TreeNode{}, 0, 0
	cur := root
	dfsBuildPreorderTree(S, &index, &level, cur)
	return root.Right
}

func dfsBuildPreorderTree(S string, index, level *int, cur *TreeNode) (newIndex *int) {
	if *index == len(S) {
		return index
	}
	if *index == 0 && *level == 0 {
		i := 0
		for i = *index; i < len(S); i++ {
			if !isDigital(S[i]) {
				break
			}
		}
		num, _ := strconv.Atoi(S[*index:i])
		tmp := &TreeNode{Val: num, Left: nil, Right: nil}
		cur.Right = tmp
		nLevel := *level + 1
		index = dfsBuildPreorderTree(S, &i, &nLevel, tmp)
		index = dfsBuildPreorderTree(S, index, &nLevel, tmp)
	}
	i := 0
	for i = *index; i < len(S); i++ {
		if isDigital(S[i]) {
			break
		}
	}
	if *level == i-*index {
		j := 0
		for j = i; j < len(S); j++ {
			if !isDigital(S[j]) {
				break
			}
		}
		num, _ := strconv.Atoi(S[i:j])
		tmp := &TreeNode{Val: num, Left: nil, Right: nil}
		if cur.Left == nil {
			cur.Left = tmp
			nLevel := *level + 1
			index = dfsBuildPreorderTree(S, &j, &nLevel, tmp)
			index = dfsBuildPreorderTree(S, index, level, cur)
		} else if cur.Right == nil {
			cur.Right = tmp
			nLevel := *level + 1
			index = dfsBuildPreorderTree(S, &j, &nLevel, tmp)
			index = dfsBuildPreorderTree(S, index, level, cur)
		}
	}
	return index
}