directory

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Nuggets team number online, help you Offer impromptu! Click for details

1. Title Description

Enter the results of preorder traversal and middle order traversal of a binary tree to reconstruct the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. For example, input preorder traversal sequence {1,2,4,7,3,5,6,8} and intermediate order traversal sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return.

Example 1

The input

,2,3,4,5,6,7 [1], [3,2,4,1,6,5,7]

The return value

,2,5,3,4,6,7 {1}

instructions

This topic contains complex data structures called TreeNode

Second, train of thought analysis

Difficulty: Medium

What this question examines is the knowledge point of tree, encounter the problem of tree commonly can use recursion method. So, this one, we’re going to do recursively today. Find the root of each recursion first, because the first element of the preceding iteration is the root. And then we do the left and right subtrees separately.

AC code

Language: the Go

Code:

package main
import . "nc_tools"
/* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */

** @param pre int int * @param vin int TreeNode */
func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
    if len(pre) == 0 {
        return nil
    }
    root := &TreeNode{Val: pre[0]}
    mid := getMiddle(vin, pre[0])
    root.Left = reConstructBinaryTree(pre[1:mid+1], vin[0:mid])
    root.Right = reConstructBinaryTree(pre[mid+1:len(pre)], vin[mid+1:len(vin)])

    return root
}
// Find the root node in the middle order traversal
func getMiddle(arr []int, val int) int {
    index := 0
    for i, v := range arr {
        if v == val {
            index = i
            return index
        }
    }
    return index
}

Copy the code

Through screenshots:

Four,

Generally encountered a tree problem is best given priority to recursive algorithm to solve, this provides a kind of idea, hope to help you all.