leetcode109 有序链表转换二叉树

本文主要是介绍leetcode109 有序链表转换二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

示例:

链接：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 有序链表转换二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！