南通六建网站,天津百度seo排名优化,wap游戏引擎,网站运营这么做给定一个单链表的头节点 head #xff0c;其中的元素 按升序排序 #xff0c;将其转换为 平衡 二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0#xff0c;-3,9#xff0c;-10,null,5]#xff0c;它表示所示的高度…给定一个单链表的头节点 head 其中的元素 按升序排序 将其转换为 平衡 二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0-3,9-10,null,5]它表示所示的高度平衡的二叉搜索树。示例 2:
输入: head []
输出: []提示:
head 中的节点数在[0, 2 * 104] 范围内-105 Node.val 10
思路先获取到链表的长度然后去递归构造树即可每次构造的树节点永远是链表或子链表的中心但是由于是单向链表所以每次获取链表中的节点的时候就会导致每次都从头开始可以用循环链表改善如果要构造的节点的坐标大于length/2的时候就next length -index次然后递归构造设置临界条件即可若length为0就是无节点如果length为1就是叶子节点。然后上代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {ListNode temp;public TreeNode sortedListToBST(ListNode head) {temp head;// 思路就是取链表的中心节点作为总树或子树的根节点然后循环、递归int length getListLength(head);return buildTree(0, length);}public TreeNode buildTree(int start ,int length) {int i 0;ListNode t temp;while (i start length/2) {t t.next;i;}// 如果是0直接为nullif (length 0) return null;// 如果length为1的时候直接返回因为它已经是树叶节点了if (length 1) return new TreeNode(t.val, null, null);// 遍历到中心节点就构造节点return new TreeNode(t.val, buildTree(start, length/2), buildTree(start length/2 1, length-1-length/2));}// 获取节点总节点数public int getListLength(ListNode head) {int length 0;while(head ! null) {length;head head.next;}return length;}}
快慢指针也是解决中间值问题的一个快速的解决办法思路相同只是取中间值的方法不同。
class Solution {public TreeNode sortedListToBST(ListNode head) {return buildTree(head, null);}public TreeNode buildTree(ListNode left, ListNode right) {if (left right) {return null;}ListNode mid getMedian(left, right);TreeNode root new TreeNode(mid.val);root.left buildTree(left, mid);root.right buildTree(mid.next, right);return root;}public ListNode getMedian(ListNode left, ListNode right) {ListNode fast left;ListNode slow left;while (fast ! right fast.next ! right) {fast fast.next;fast fast.next;slow slow.next;}return slow;}
}
