首页 > 代码库 > 【原创】leetCodeOj ---Convert Sorted List to Binary Search Tree 解题报告

【原创】leetCodeOj ---Convert Sorted List to Binary Search Tree 解题报告

原题地址:

https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

 

题目内容:

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

 

方法:

单纯。如何安排插入顺序,使得一棵二叉排序树接近平衡?

你从中间开始插嘛。这样左子树和右子树之差或者为0,或者为1。

所以,这个问题的本质是找链表的中间节点。

找到中间节点后,递归产生左子树和右子树,在找左边子链表的中间节点和右边子链表的中间节点即可。

当然啦,最后返回中间节点。

 

全部代码:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; next = null; } * } *//** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode sortedListToBST(ListNode head) {        int len = countLen(head);        if (len == 0)            return null;        return constructTree(head,len); // len is the number of nodes in list.    }        private TreeNode constructTree(ListNode head,int len)    {        if (head == null || len <= 0)            return null;        int mid = len / 2 + 1;        TreeNode tmp = new TreeNode(head.val);        tmp.left = null;        tmp.right = null;        if (mid == 0)            return tmp;        ListNode tar = findMidNode(head,mid);        tmp.val = tar.val;        tmp.left = constructTree(head,mid - 1);        tmp.right = constructTree(tar.next,len - mid);        return tmp;    }        private ListNode findMidNode(ListNode head,int mid)    {        int count = 1;        while (mid != count++)            head = head.next;        return head;    }        private int countLen(ListNode head)    {        int len = 0;        while (head != null)        {            len ++;            head = head.next;        }        return len;    }}

 

【原创】leetCodeOj ---Convert Sorted List to Binary Search Tree 解题报告