将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / -3 9 / / -10 5
思路1: 遍历链表,获得链表长度,找到链表中间的值,形成根结点,根据left,right ,递归寻找结点的左子树和右子树。
因为每次递归都要遍历链表,时间复杂度非常高,
/** * 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; ListNode l1=head,l2=head; int count=0; while(l1!=null){ l1=l1.next; count++; //得到链表的长度 } // for(int i=0;i<count/2;i++){ // l2=l2.next; //得到链表的中点 // } return buildBST(head,0,count-1); } public TreeNode buildBST(ListNode head,int l,int r){ if(l>r)return null; int mid=(l+r)/2; ListNode tem=head; for(int i=0;i<mid;i++)tem=tem.next; //每次递归都要遍历链表 TreeNode root=new TreeNode(tem.val); root.left=buildBST(head,l,mid-1); root.right=buildBST(head,mid+1,r); return root; } }
思路2:先转化为数组,再转化为有序数组转换二叉探索树。
参考:
leetcode- 将有序数组转换为二叉搜索树(java)
class Solution { public TreeNode sortedListToBST(ListNode head) { if(head==null)return null; int count=0; ListNode l1=head; while(l1!=null){ l1=l1.next; count++; } int[] nums=new int[count]; for(int i=0;i<count;i++){ nums[i]=head.val; head=head.next; //转化为数组 } return buildBST(nums,0,count-1); //将排序数组转为二叉探索树 } public TreeNode buildBST(int[] nums,int l,int r){ if(l>r)return null; int mid=(l+r)/2; TreeNode root=new TreeNode(nums[mid]); root.left=buildBST(nums,l,mid-1); root.right=buildBST(nums,mid+1,r); return root; } }
新的思路:
使用快慢指针解决,慢指针遍历之后处于链表中间位置,slow位置就是根结点,slow->next就是二叉树的右子树,
左边就是左子树。 要将左子树和右子树之间的链表断裂last.next=null ,fast=slow.next; 左右子树都不包含根结点
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,last=slow; while(fast.next!=null&&fast.next.next!=null){ last=slow; //这里执行到最后一步的时候,last只比slow慢一个指针。 slow=slow.next; fast=fast.next.next; } TreeNode root=new TreeNode(slow.val); fast=slow.next;//fast部分的链表转化为右子树 if(slow!=last){ last.next=null; root.left=sortedListToBST(head); } root.right=sortedListToBST(fast); return root; } }