重庆网站推广服务seo排名工具有哪些

一、需求

• 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树；

• 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1；

二、快慢指针

2.1  思路分析

1. 对于有序链表，要想找到它的中间元素，需要利用快慢指针，每次快指针比慢指针多走一格，当快指针指向null或者快指针的下一个元素指向null的时候，此时慢指针指向的就是中间元素；
2. 除了步骤1，基本思想与"有序数组转换为二叉搜索树"一致；

2.2  代码实现

class Solution {public TreeNode sortedListToBST(ListNode head) {if(head == null) return null;return helper(head, null);}//符合左闭右开public TreeNode helper(ListNode head, ListNode tail) {if(head == tail) return null;ListNode fast = head;ListNode slow = head;while(fast != tail && fast.next != tail) {fast = fast.next.next;slow = slow.next;}TreeNode root = new TreeNode(slow.val);root.left = helper(head, slow);root.right = helper(slow.next, tail);return root;}
}

2.3  复杂度分析

• 时间复杂度为O(N)，建立二叉搜索树需要遍历所有的链表节点；
• 空间复杂度为；