首页 > 代码库 > leetcode--Convert Sorted List to Binary Search Tree

leetcode--Convert Sorted List to Binary Search Tree

2024-07-07 08:47:47   229人阅读

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    /** Convert the linked list to arrayList first, and then convert the ArrayList to a BST
     * @param head  --head node of the linked list
     * @return TreeNode --the root node of a height balanced BST tree
     * @author Averill Zheng
     * @version 2014-06-05
     * @since JDK 1.7
     */
    public TreeNode sortedListToBST(ListNode head) {
        TreeNode root = null;
        ArrayList<Integer> number = new ArrayList<Integer>();
        int length = 0;
        while(head != null){
            number.add(head.val);
            head = head.next;
            ++length;
        }
        root = convertHelper(number, 0, length);
        return root;
    }
    private TreeNode convertHelper(ArrayList<Integer> number, int i, int j){
        TreeNode root = null;
        if(j > i){
            if(j == i + 1)
                root = new TreeNode(number.get(i));
            else{
                int mid = i + (j - i) / 2;
                root = new TreeNode(number.get(mid));
                root.left = convertHelper(number,i, mid);
                root.right = convertHelper(number, mid + 1, j);
            }
        }
        return root;   
    }
}

　　


联系
我们