How to convert an ordered array to a binary search tree

This article will explain in detail how to convert an ordered array into a binary search tree. The content of the article is of high quality. Therefore, Xiaobian shares it with you as a reference. I hope you have a certain understanding of relevant knowledge after reading this article.

Algorithm:

The core idea is to use dichotomy, but ordered arrays and ordered lists do not find the middle node in the same way.

1. For ordered arrays or ordered lists, consider the middle node as the root node 2. The values of the left array are less than the root node, as the left subtree; the values of the right array are greater than the root node, as the right subtree. 3. Recursively process the left and right subtrees until only one node remains.

Topic 1:

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

Code implementation:

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func sortedArrayToBST(nums []int) *TreeNode { if len(nums) == 0 { return nil } mid := len(nums)/2 root := new(TreeNode) root.Val = nums[mid] root.Left = sortedArrayToBST(nums[:mid]) root.Right = sortedArrayToBST(nums[mid+1:]) return root}//Algorithm: The core idea is to use dichotomy. For ordered arrays, the middle node is regarded as the root node.//The values of the left array are all less than the root node, which is regarded as the left subtree;//The values of the right array are all greater than the root node, which is regarded as the right subtree.// Recursively process the left and right subtrees until only one node remains.

Implementation results:

Topic 2:

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

Code implementation:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } *//** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func sortedListToBST(head *ListNode) *TreeNode { if head == nil { return nil } if head.Next == nil { return &TreeNode{Val:head.Val} } //Tip: It is convenient to find the predecessor node of the middle node in a loop, sentinel s := new(ListNode) s.Next = head f := head for f != nil && f.Next != nil { //essence: fast and slow pointer, 1 step, 2 steps are exactly two equal parts, can be extended to three equal parts, n equal parts s = s.Next f = f.Next.Next } res := new(TreeNode) res.Val = s.Next.Val r := s.Next.Next s.Next = nil //The left half is a separate linked list res.Left = sortedListToBST(head) res.Right = sortedListToBST(r) return res}//Algorithm: Use the dichotomy method.//After finding the middle node, divide the list into two. Continue to construct the left subtree and the right subtree.//Recursively process until all nodes are processed.

Implementation results:

How to convert an ordered array into a binary search tree is shared here. I hope the above content can be of some help to everyone and learn more knowledge. If you think the article is good, you can share it so that more people can see it.