题目来源

109. 有序链表转换二叉搜索树

题目描述

类似的题目：108. 将有序数组转换为二叉搜索树

题目解析

递归

跟108. 将有序数组转换为二叉搜索树不同的是，数组取中很容易使用下标得到，但是链表没那么容易，不过我们可以使用快慢指针来取得终点。当获取到链表的中点作为而二叉树节点的时候，我们还需要得到该节点的左右子树
由于我们得到的是一个有序链表而不是数组，我们不能直接使用下标来访问元素。我们需要知道链表中的中间元素。
我们可以利用两个指针来访问链表中的中间元素。假设我们有两个指针 slow_ptr 和 fast_ptr。slow_ptr 每次向后移动一个节点而 fast_ptr 每次移动两个节点。当 fast_ptr 到链表的末尾时 slow_ptr 就访问到链表的中间元素。对于一个偶数长度的数组，中间两个元素都可用来作二叉搜索树的根。
当找到链表中的中间元素后，我们将链表从中间元素的左侧断开，做法是使用一个 prev_ptr 的指针记录 slow_ptr 之前的元素，也就是满足 prev_ptr.next = slow_ptr。断开左侧部分就是让 prev_ptr.next = None。
我们只需要将链表的头指针传递给转换函数，进行高度平衡二叉搜索树的转换。所以递归调用的时候，左半部分我们传递原始的头指针；右半部分传递 slow_ptr.next 作为头指针。

一个很容易出错的点：当链表中只有一个节点的时候就要及时返回，因为它是无法通过快慢指针取中的，只会进入死循环

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode sortedListToBST(ListNode head) {if (head == null){return null;}if (head.next == null){return new TreeNode(head.val);}ListNode fast = head, slow = head, pre = head;while (fast != null && fast.next != null){fast = fast.next.next;pre = slow;slow = slow.next;}pre.next = null;TreeNode node = new TreeNode(slow.val);node.left = sortedListToBST(head);node.right = sortedListToBST(slow.next);return  node ;}
}

使用半开半闭区间

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public   TreeNode sortedListToBST(ListNode head) {return  helper(head,  null) ;}private TreeNode helper(ListNode head, ListNode tail){if (head == tail){return null;}ListNode fast = head, slow = head;while (fast != tail && fast.next != tail){slow = slow.next;fast = fast.next.next;}TreeNode node = new TreeNode(slow.val);node.left = helper(head, slow);node.right = helper(slow.next, tail);return node;}
}

转换为数组然后BST

索引作为参数，就是参数，不要一下子长度一下子索引

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private  ArrayList<Integer> arrayList;public Solution() {arrayList = new ArrayList<>();}// 转换为数组，然后转为BSTpublic  TreeNode sortedListToBST(ListNode head) {while (head != null){arrayList.add(head.val);head = head.next;}return  arrayListToBST(0,  arrayList.size() - 1) ;}public  TreeNode arrayListToBST(int left, int right){if (right < left){return null;}int mid = left + (right - left)/2;TreeNode node = new TreeNode(arrayList.get(mid));node.left = arrayListToBST(left, mid - 1);node.right = arrayListToBST(mid + 1, right);return node;}
}

中序遍历模拟

因为我们知道题目给定的升序数组，其实就是二叉搜索树的中序遍历。那么我们完全可以按照这个顺序去为每个节点赋值。

实现的话，我们套用中序遍历的递归过程，并且将start和end作为递归参数，当start == end的时候，就返回null

先回想一下中序遍历的算法

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();getAns(root, ans);return ans;
}private void getAns(TreeNode node, List<Integer> ans) {if (node == null) {return;}getAns(node.left, ans); ans.add(node.val);getAns(node.right, ans);
}

之前是将node和val进行保存，这里的话我们是给当前节点仅需赋值，为了实现一次赋值，我们需要一个cur指针指向给定的数列，每赋一个值就进行后移。

ListNode cur = null;public TreeNode sortedListToBST(ListNode head) {cur = head;int end = 0;while (head != null) {end++;head = head.next;}return sortedArrayToBSTHelper(0, end);
}private TreeNode sortedArrayToBSTHelper(int start, int end) {if (start == end) {return null;}int mid = (start + end) >>> 1;//遍历左子树并且将根节点返回TreeNode left = sortedArrayToBSTHelper(start, mid);//遍历当前根节点并进行赋值TreeNode root = new TreeNode(cur.val);root.left = left;cur = cur.next; //指针后移，进行下一次的赋值//遍历右子树并且将根节点返回TreeNode right = sortedArrayToBSTHelper(mid + 1, end);root.right = right;return root;
}