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

有序链表转换二叉搜索树

题目描述：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

首先，将链表转化成数组，然后处理过程就和 LeetCode-108-将有序数组转换为二叉搜索树的解法完全一样了。
【LeetCode-109-有序链表转换二叉搜索树】根据二叉搜索树的性质，因为给定的数组是按升序排列的，所以可以确定数组num即为该二叉搜索树的中序遍历序列，为了得到一颗平衡的二叉树，取数组中间位置的节点作为根节点，这样，左右子树的节点较为平衡，具体处理过程如下：

调用递归方法，初始的起始位置为数组的长度；

当起点位置大于终点位置时，说明节点已经遍历完了，直接返回空树；

获取中间位置的值作为根节点，这样左右子树的节点树是比较均衡的；

然后递归获得当前根节点的左右子树；

最后返回根节点即为平衡的二叉搜索树。

import com.kaesar.leetcode.ListNode; import com.kaesar.leetcode.TreeNode; import java.util.LinkedList; import java.util.Queue; public class LeetCode_109 { public static TreeNode sortedListToBST(ListNode head) { Queue queue = new LinkedList<>(); while (head != null) { queue.add(head.val); head = head.next; } int[] nums = new int[queue.size()]; int index = 0; // 先将链表转换成数组，即为二叉树的中序遍历序列 while (!queue.isEmpty()) { nums[index++] = queue.poll(); } // 调用递归方法，初始的起始位置为数组的长度 return sortedListToBST(nums, 0, nums.length - 1); }/** * 递归 * * @param nums * @param left * @param right * @return */ private static TreeNode sortedListToBST(int[] nums, int left, int right) { // 当起点位置大于终点位置时，说明节点已经遍历完了，直接返回空树 if (left > right) { return null; } // 获取中间位置的值作为根节点，这样左右子树的节点树是较为平衡点 int mid = (left + right) / 2; TreeNode root = new TreeNode(nums[mid]); // 然后递归获得当前根节点的左右子树 root.left = sortedListToBST(nums, left, mid - 1); root.right = sortedListToBST(nums, mid + 1, right); return root; }public static void main(String[] args) { ListNode head = new ListNode(-10); head.next = new ListNode(-3); head.next.next = new ListNode(-0); head.next.next.next = new ListNode(5); head.next.next.next.next = new ListNode(9); sortedListToBST(head).print(); } }