Convert Sorted List to Binary Search Tree「建议收藏」

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.
想了好久想不出来。后来看了题目分类里面说是DFS,可是没有想出DFS的算法来。后来想到了一个递归的方法。可是空间和时间都是O(n)。
后来网上找了一个空间是O(1)的时间是O(n)的算法,是一种新的解题思路,用的是中递归。

一般我解题都是用的头递归或者尾递归。第一次见识到了中递归,相当于把递归当成了一个循环体,用引用来作为变量,每一个递归中改动,须要非常强大的想象力。把整个递归树在脑子里想清楚。

空间和时间都为O(n):

    TreeNode *sortedListToBST(ListNode *head) 
	{
		vector<TreeNode*> treeNodes;
		while (head != NULL)
		{
			TreeNode *node = new TreeNode(head->val);
			treeNodes.push_back(node);
			head = head->next;
		}
		return genBST(0, treeNodes.size()-1, treeNodes);
    }
	
	TreeNode* genBST(int start, int end, vector<TreeNode*> &treeNodes)
	{
		if (start == end) return treeNodes[start];
		else if (start+1 == end)
		{
			treeNodes[start]->right = treeNodes[end];
			return treeNodes[start];
		} 

		int mid = (start+end)/2;
		TreeNode* root = treeNodes[mid];
		root->left = genBST(start, mid-1, treeNodes);
		root->right = genBST(mid+1, end, treeNodes);
		return root;
	}

空间为O(1)时间为O(n):

	TreeNode *sortedListToBST(ListNode *head)
	{
	    int len = 0;
        ListNode * node = head;
        while (node != NULL)
        {
            node = node->next;
            len++;
        }
        return buildTree(head, 0, len-1);
    }
    
    TreeNode *buildTree(ListNode *&node, int start, int end)
    {
        if (start > end) return NULL;
        int mid = start + (end - start)/2;
        TreeNode *left = buildTree(node, start, mid-1);
        TreeNode *root = new TreeNode(node->val);
        root->left = left;
        node = node->next;
        root->right = buildTree(node, mid+1, end);
        return root;
    }

解法引用:http://www.bwscitech.com/a/jishuzixun/javayuyan/2013/0930/15822.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115955.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Xray基础使用介绍

    Xray基础使用介绍官方使用文档:https://docs.xray.cool/#xray简介xray是一款功能强大的安全评估工具,由多名经验丰富的一线安全从业者呕心打造而成,主要特性有:检测速度快。发包速度快;漏洞检测算法高效。支持范围广。大至OWASPTop10通用漏洞检测,小至各种CMS框架POC,均可以支持。代码质量高。编写代码的人员素质高,通过CodeReview、单元测试、集成测试等多层验证来提高代码可靠性。高级可定制。通过配置文件暴露了引擎的各种参数,通过修改配置文件可以极大的客

  • android 画图 平面图,房屋平面图 DIY 神工具!「MagicPlan」用手机拍照就自动帮你画好(iPhone, Android)…

    android 画图 平面图,房屋平面图 DIY 神工具!「MagicPlan」用手机拍照就自动帮你画好(iPhone, Android)…不论是新屋装潢还是老屋改装,为了省下设计费,许多人都会想自己动手画平面图,但是如果本身没有相关的底子,从怎么开始动手测量尺寸到画出完整的全屋平面图,每个点都有让人不知所措的地方。来!免惊~「MagicPlan」快拿去用!它简直就是我们这种无设计底子平凡人的救星,只要拿着手机或平板拍几张照,房屋或房间的平面图就完成啦!什么?你说听起来很神吗?没错它就是这么神呀!完全不需测量、不需自己拿笔尺绘制、不需…

  • Java Metric 入门详解

    Java Metric 入门详解翻译自:http://metrics.dropwizard.io/3.1.0/getting-started/    待完成……

  • 原生sql和 TP sql怎么关联?

    原生sql和 TP sql怎么关联?

    2021年10月23日
  • html样式表优点,css样式表的使用有哪些优点?

    html样式表优点,css样式表的使用有哪些优点?CSS全称CascadingStyleSheet,表示层叠样式表,是一种用来表现HTML(标准通用标记语言的一个应用)或XML(标准通用标记语言的一个子集)等文件样式的计算机语言。CSS不仅可以静态地修饰网页,还可以配合各种脚本语言动态地对网页各元素进行格式化CSS用于改进HTML标记内容的呈现。使用CSS我们可以基于媒体定义不同的内容显示方式。CSS能够对网页中元素位置的排版进行像素级精确…

  • Android SDK 安装及环境配置教程

    Android SDK 安装及环境配置教程1、配置jdk,查看jdk是否存在,一般电脑上都已经安装了的2、AndroidSDK下载官网下载:https://android-sdk.en.softonic.com/download找到下载

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号