describe

The binary tree is constructed according to the pre-order traversal and middle-order traversal of a tree

Note:

You can assume that there are no repeating elements in the tree.

For example, given

Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the code

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Train of thought

  • In a sequential traversal, the first node is the root node
  • In middle-order traversal, the position of the first node is found. The L data in front of the root node is the middle-order traversal data of the left subtree of the root node, and the L data behind the root node is the pre-order traversal of the left subtree
  • Same as above for the right subtree
  • In short, the root node is determined, the data of the left and right subtrees are determined, and the left and right subtrees are reconstructed recursively

Code implementation

// Build a binary tree according to the pre-order traversal and middle-order traversal of a tree

// TreeNode Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}

	// The root node is the first node in the forward traversal
	res := &TreeNode{
		Val: preorder[0],}if len(preorder) == 1 {
		return res
	}

	// In a middle-order traversal, the node before the root node is the left subtree, and the node after the root node is the right subtree

	// Anonymous function
	idx := func(val int, nums []int) int {
		for i, v := range nums {
			if v == val {
				return i
			}
		}
		return - 1
	}(res.Val, inorder)
	if idx == - 1 {
		panic("data error")}// Construct the left and right subtrees of the root node recursively
	res.Left = buildTree(preorder[1:idx+1], inorder[:idx])
	res.Right = buildTree(preorder[idx+1:], inorder[idx+1:)return res
}
Copy the code

Title source

105. Construct a binary tree by traversing pre-order and middle-order sequences

GitHub

  • Source code portal
  • Various data structure and algorithm implementation, LeetCode solution ideas and answers
  • Big factory interview questions summary and answer analysis

This is an original article. Please scan the code to follow the public account Loulan or the website Lovecoding. club. Please read the following wonderful articles in the first time.