原题
- 题目描述: 把一个升序链表构建成左右子树深度相差不过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) {
if(head==null){
return null;
}
return buildBST(head,null);
}
public TreeNode buildBST(ListNode head,ListNode tail){
ListNode fast=head;
ListNode slow=head;
if(head==tail){//当头尾相遇时返回空
return null;
}
while(fast!=tail&&fast.next!=tail){//快指针指向尾结点和其前驱结点时结束
fast=fast.next.next;
slow=slow.next;
}
TreeNode treeNode=new TreeNode(slow.val);//根节点(值为慢指针的值,取自有序链表的中间值)
treeNode.left=buildBST(head,slow);//链表前半段放左子树
treeNode.right=buildBST(slow.next,tail);//链表后半段放右子树
return treeNode;//返回树的根节点
}
}