[LeetCode]109.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.

【分析】

无

【代码】

在下面超时的代码上进行改进：把链表先转换为vector再进行操作。

[LeetCode]108.Convert Sorted Array to Binary Search Tree

/*********************************
*   日期：2014-12-29
*   作者：SJF0115
*   题目: 109.Convert Sorted List to Binary Search Tree
*   来源：https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 链表节点
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};
// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL){
            return NULL;
        }//if
        vector<int> vec;
        // 统计个数
        int count = 0;
        ListNode *p = head;
        while(p){
            count++;
            vec.push_back(p->val);
            p = p->next;
        }//while
        // 分治 递归
        return sortedListToBST(vec,0,count-1);
    }
private:
   TreeNode *sortedListToBST(vector<int>& vec,int start,int end) {
       if(start > end){
           return NULL;
       }//if
       int mid = (start + end) / 2;
       // 以中间节点为根节点
       TreeNode *root = new TreeNode(vec[mid]);
       // 以[start,mid-1]为左子树
       TreeNode *leftSubTree = sortedListToBST(vec,start,mid-1);
       // 以[mid+1,end]为右子树
       TreeNode *rightSubTree = sortedListToBST(vec,mid+1,end);
       root->left = leftSubTree;
       root->right = rightSubTree;
       return root;
   }
};
// 层次遍历
vector<vector<int> > LevelOrder(TreeNode *root) {
    vector<int> level;
    vector<vector<int> > levels;
    if(root == NULL){
        return levels;
    }
    queue<TreeNode*> cur,next;
    //入队列
    cur.push(root);
    // 层次遍历
    while(!cur.empty()){
        //当前层遍历
        while(!cur.empty()){
            TreeNode *p = cur.front();
            cur.pop();
            level.push_back(p->val);
            // next保存下一层节点
            //左子树
            if(p->left){
                next.push(p->left);
            }
            //右子树
            if(p->right){
                next.push(p->right);
            }
        }
        levels.push_back(level);
        level.clear();
        swap(next,cur);
    }//while
    return levels;
}
// 创建链表
ListNode* CreateList(vector<int> num){
    ListNode *head = NULL;
    int len = num.size();
    if(len == 0){
        return head;
    }//if
    // 创建链表
    ListNode *node,*p;
    head = new ListNode(num[0]);
    p = head;
    for(int i = 1;i < len;i++){
        node = new ListNode(num[i]);
        p->next = node;
        p = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector<int> num = {1,3,5,6,7,13,20};
    // 创建链表
    ListNode* head = CreateList(num);
    // 创建平衡二叉树
    TreeNode* root = solution.sortedListToBST(head);
    // 层次输出检验
    vector<vector<int> > levels = LevelOrder(root);
    for(int i = 0;i < levels.size();i++){
        for(int j = 0;j < levels[i].size();j++){
            cout<<levels[i][j]<<" ";
        }
        cout<<endl;
    }
}

【代码二】

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head){
        if(head == NULL){
            return NULL;
        }//if
	    int count = 0;
        ListNode *p = head;
        // 统计链表个数
        while(p){
            p = p->next;
            count++;
        }//while
        return SortedListToBST(head,0,count-1);
    }
private:
    TreeNode *SortedListToBST(ListNode*& node,int start,int end){
        if (start > end){
            return NULL;
        }//if
        // 中间节点
        int mid = start + (end - start)/2;
        // 左子树
        TreeNode *leftSubTree = SortedListToBST(node, start, mid-1);
        TreeNode *root = new TreeNode(node->val);
        root->left = leftSubTree;
        node = node->next;
        // 右子树
        TreeNode *rightSubTree = SortedListToBST(node, mid+1, end);
        root->right = rightSubTree;
        return root;
    }
};

这是一中自底向上的方法。

在递归中传的都是同一个链表，只是这个链表的节点不停往前走；而真正决定性变化的是区间；

可以看到，每次递归调用开始时，节点指针都指向区间第一个，结束时节点的指针指向区间末尾的后一个。

每次递归调用时，分成左右两部分，左边构造完时，正好指针指向mid，创建一下root，继续构造右部分子树。

【错解】

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL){
            return NULL;
        }//if
        // 统计个数
        int count = 0;
        ListNode *p = head;
        while(p){
            count++;
            p = p->next;
        }//while
        // 分治 递归
        return sortedListToBST(head,1,count);
    }
private:
   TreeNode *sortedListToBST(ListNode* head,int start,int end) {
       if(start > end){
           return NULL;
       }//if
       int mid = (start + end) / 2;
       // 寻找第mid个节点
       ListNode *p = head;
       int index = 1;
       while(index != mid){
            index++;
            p = p->next;
       }//while
       // 以中间节点为根节点
       TreeNode *root = new TreeNode(p->val);
       // 以[start,mid-1]为左子树
       TreeNode *leftSubTree = sortedListToBST(head,start,mid-1);
       // 以[mid+1,end]为右子树
       TreeNode *rightSubTree = sortedListToBST(head,mid+1,end);
       root->left = leftSubTree;
       root->right = rightSubTree;
       return root;
   }
};

我们首先想到的肯定是这种比较笨的方法。但是这种方法超时。