学校网站源码,合肥seo按天收费,乐装网,家具网站源码给定一个单链表#xff0c;其中的元素按升序排序#xff0c;将其转换为高度平衡的二叉搜索树。
本题中#xff0c;一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
解题思路
先将链表转换成数组#xff0c;再构造二叉搜索树
代码 …给定一个单链表其中的元素按升序排序将其转换为高度平衡的二叉搜索树。
本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
解题思路
先将链表转换成数组再构造二叉搜索树
代码
/*** 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) {ArrayListInteger listnew ArrayList();while (head!null){list.add(head.val);head head.next;}int[] knew int[list.size()];for(int c0;ck.length;c)k[c]list.get(c);return sortedArrayToBST(k);}public TreeNode sortedArrayToBST(int[] nums) {if(nums.length0) return null;return BST(nums,0,nums.length-1);}public TreeNode BST(int[] nums,int left,int right) {if(leftright) return null;if(leftright) return new TreeNode(nums[left]);int midleft((right-left)1);TreeNode treeNodenew TreeNode(nums[mid]);treeNode.rightBST(nums,mid1,right);treeNode.leftBST(nums,left,mid-1);return treeNode;}
}解题思路
通过快慢指针找链表的中点进行递归
代码 class Solution {public TreeNode sortedListToBST(ListNode head) {if(headnull) return null;return helper(head,null);}public TreeNode helper(ListNode head,ListNode tail) {if(headtail) return null;ListNode slowhead,fasthead;while (fast!tailfast.next!tail){fastfast.next.next;slowslow.next;}TreeNode treeNodenew TreeNode(slow.val);treeNode.righthelper(slow.next,tail);treeNode.lefthelper(head,slow);return treeNode;}
}
