Convert Sorted List to Binary Search Tree

今天是一道有关链表和二叉树的题目，来自LeetCode，难度为Medium，Acceptance为26%。

题目如下

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

Example

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

首先，该题还是有难度的，但是我们换一个思路可能就会简单很多，即如果是将一个排序二叉树转换成链表，相信大多数同学都会做，无非是一个中序遍历。

那么，这里讲链表转换成二叉树也是一样的思路，即一个中序遍历，其具体思路如下。

按照中序遍历的思路，应该先生成左子树，然后是根节点，最后的右子树。那么，很明显这是一个递归的结构。那么剩下的问题就是如何确定递归的终止条件。

因为在转换的过程中，需要计算各子链表的长度，那么这里就可以由此来终止递归，即当长度等于0时终止。下面我们来看代码。

代码如下

C++版

class Solution {
public:
    ListNode *list;
    int count(ListNode *node){
        int size = 0;
        while (node) {
            ++size;
            node = node->next;
        }
        return size;
    }

    TreeNode *generate(int n){
        if (n == 0)
            return NULL;
        TreeNode *node = new TreeNode(0);
        node->left = generate(n / 2);
        node->val = list->val;
        list = list->next;
        node->right = generate(n - n / 2 - 1);
        return node;
    }

    TreeNode *sortedListToBST(ListNode *head) {
        this->list = head;
        return generate(count(head));
    }
};

java版

private ListNode node;

public TreeNode sortedListToBST(ListNode head) {
    if(head == null){
        return null;
    }

    int size = 0;
    ListNode runner = head;
    node = head;

    while(runner != null){
        runner = runner.next;
        size ++;
    }

    return inorderHelper(0, size - 1);
}

public TreeNode inorderHelper(int start, int end){
    if(start > end){
        return null;
    }

    int mid = start + (end - start) / 2;
    TreeNode left = inorderHelper(start, mid - 1);

    TreeNode treenode = new TreeNode(node.val);
    treenode.left = left;
    node = node.next;

    TreeNode right = inorderHelper(mid + 1, end);
    treenode.right = right;

    return treenode;
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image