leetcode109 有序链表转换二叉树

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

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

示例:

leetcode109 有序链表转换二叉树
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
平衡链表有很多种
注意一点,二叉排序树中序遍历是从小到大的。

public TreeNode sortedListToBST(ListNode head) {
        if(head==null)
            return null;
        ListNode cur=head;
        ArrayList<Integer> arr= new ArrayList<>();
        while (cur!=null)
        {
            arr.add(cur.val);
            cur=cur.next;
        }
        return RecurBuid(0,arr.size()-1,arr);
    }
    public TreeNode RecurBuid(int start,int end,ArrayList<Integer> arr)
    {
        if(start>end)
            return null;
        int mid=start+((end-start)>>1);
        TreeNode root=new TreeNode(arr.get(mid));
        root.left=RecurBuid(start,mid-1,arr);
        root.right=RecurBuid(mid+1,end,arr);

        return root;
    }

leetcode109 有序链表转换二叉树

上一篇:敏捷估算


下一篇:如何保持DIV的垂直滚动条在底部