Shulou(Shulou.com)05/31 Report--

This article mainly explains "how C++ turns an ordered linked list into a binary search tree". The content in the article is simple and clear, and it is easy to learn and understand. let's study and learn "how C++ turns an ordered linked list into a binary search tree".

Convert ordered linked list to binary search tree

Example:

Given the sorted linked list: [- 10fui 3meme 0pr 5je 9]

One possible answer is: [0jimi 3je 9je Lou 10ju nulljue 5], which represents the following height balanced BST:

0

/

-3 9

/ /

-10 5

This problem requires that the ordered linked list be converted into a binary search tree, which is exactly the same as the previous Convert Sorted Array to Binary Search Tree, except that the data type of the operation is different, one is the array, the other is the linked list. Arrays are convenient because you can access any element directly through index, but not linked lists. Because the binary search method needs to find the midpoint every time, and the middle point of the linked list can be operated by fast and slow pointers, see the previous two blogs Reorder List and Linked List Cycle II about the application of fast and slow pointers. After finding the midpoint, we need to establish the root node of a number with the value of the midpoint, and then we need to break the original chain list and divide it into two linked lists, neither of which can contain the original node, and then recursively call the original function to the two chain lists and connect the left and right child nodes respectively. The code is as follows:

Solution 1:

Class Solution {public: TreeNode * sortedListToBST (ListNode* head) {if (! head) return NULL; if (! head- > next) return new TreeNode (head- > val); ListNode* slow = head, * fast = head, * last = slow; while (fast- > next & & fast- > next- > next) {last = slow; slow = slow- > next; fast = fast- > next- > next } fast = slow- > next; last- > next = NULL; TreeNode * cur = new TreeNode (slow- > val); if (head! = slow) cur- > left = sortedListToBST (head); cur- > right = sortedListToBST (fast); return cur;}}

We can also use the following recursive method to rewrite a recursive function with two input parameters, the starting point and the end point of the sublinked list, because we know these two points, the range of the linked list can be determined, and the middle part can be directly converted into a binary search tree. The content of the recursive function is very similar to that in the above solution. See the code as follows:

Solution 2:

Class Solution {public: TreeNode* sortedListToBST (ListNode* head) {if (! head) return NULL; return helper (head, NULL);} TreeNode* helper (ListNode* head, ListNode* tail) {if (head = = tail) return NULL; ListNode* slow = head, * fast = head; while (fast! = tail & & fast- > next! = tail) {slow = slow- > next Fast = fast- > next- > next;} TreeNode * cur = new TreeNode (slow- > val); cur- > left = helper (head, slow); cur- > right = helper (slow- > next, tail); return cur;}} Thank you for your reading, the above is the content of "how C++ turns the ordered linked list into a binary search tree". After the study of this article, I believe you have a deeper understanding of the problem of how C++ turns the ordered linked list into a binary search tree. the specific use also needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.