Leetcode109.有序链表转换二叉搜索树

1.题目描述

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

  	  0
     / \
   -3   9
   /   /
 -10  5

2.解答

首先根据高度平衡这个字眼,可以发现,这颗二叉树的根节点一定是链表的中间节点,如果链表数目为偶数,那么偏左和偏右都可以,因为链表不同于数组,不能进行随机访问,那么就需要通过遍历链表的方式找到中间节点,最常用的方式就是快慢指针,之前已经通过几种方法完成了中间节点问题,我的整体解题思路是正确的,但是最后在

sortedListToBST(ListNode head)方法中的一些细节没有处理好,我的解题过程停止在了这里,可惜了啊,看了一眼答案立马知道怎么做了。

/**
 * 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 mid = findMiddle(head);
        //建立根节点,要注意TreeNode和ListNode是不一样的
        TreeNode root = new TreeNode(mid.val);
        //如果子树只剩下一个节点,那么直接返回
        if(head == mid) return root;
        //递归连接
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    private ListNode findMiddle(ListNode head){
        if(head == null)    return null;
        ListNode p1 = head,p2 = head,prev = null;
        while(p2 != null && p2.next != null){
            prev = p1;
            p1 = p1.next;
            p2 = p2.next.next;
        }
        if(prev != null)    prev.next = null;
        return p1;
    }
}

上面说到,链表是不能进行随机读取的,数组可以,那么这种方法中,我们就把所有的链表节点全部放在数组中,使用空间换取时间的方法,这样就可以对节点进行随机读取,同样是采用递归的方法,这一次加深了对判定条件

if(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 {
    private List<ListNode> list;
    public Solution(){
        list = new ArrayList<>();
    }
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)    return null;
        ListNode p = head;
        while(p != null){
            list.add(p);
            p = p.next;
        }
        return helper(list,0,list.size()-1);
    }
    public TreeNode helper(List<ListNode> list,int left,int right){
        if(left > right)    return null;
        int midIndex = (left + right) / 2;
        TreeNode root = new TreeNode(list.get(midIndex).val);
        if(left == right)   return  root;
        root.left = helper(list,left,midIndex-1);
        root.right = helper(list,midIndex+1,right);
        return root;
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode109有序链表转换二叉搜索树md