【题目】
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;
}
};
我们首先想到的肯定是这种比较笨的方法。但是这种方法超时。
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 后端.zip
Leetcode101.zip
My Solutions to Leetcode problems. All solutions support C
刷leetcode总结.md
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi