文档章节

108. Convert Sorted Array to Binary Search Tree

cofama
 cofama
发布于 2017/02/27 22:42
字数 862
阅读 1
收藏 0
点赞 0
评论 0

原题连接

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

将一个已经排好序的数组转化为一棵平衡二分搜索树,我最先想到是用递归,但我又不想用递归,所以用了一种类似广度优先搜索的方法。需要新建一个vector来存放TreeNode的指针。

因为数组已经是有序的,所以根节点选择数组的中间元素,如果数组大小是偶数,则选择最中间两个元素中序号较大的那个。根节点TreeNode的val赋值为对应数组元素的序号,而不是元素值,因为用元素值的话不能体现元素间的顺序的相对关系。然后把根节点push到vector中。

然后进入循环阶段,遍历vector,通过val可以获得当前树节点对应的数组序号mid,并以mid为界将数组划分为左右两个区间。以根节点为例,当前整个区间的上下界分别为0和n-1,左区间为[0,mid-1],右区间为[mid+1,n-1],那么左儿子和右儿子分别为左右两个区间的中间元素。如果计算出来的儿子序号不在区间内(这在区间长度为0或1时有可能发生),就直接把它赋值为NULL,否则新建TreeNode,并把val值赋为序号。把左儿子的right指针指向当前节点,left指针指向当前节点的left指针;右儿子的left指针指向当前节点,right指针指向当前节点的right指针。这几个操作是为了确定左右儿子要划分的数组区间,比较难解释,还是上张图: 输入图片说明

当前节点的left、right指针分别指向它的左右儿子,把左右儿子依次添加到vector中。进入下一个循环,取vector中的下一个节点,节点划分的数组区间上下界就要由left、right指针来决定了。如上图所示,left指向的节点的val值加1是区间下界,right指向的节点的val值减一是区间上界。会存在left或right指向NULL的情况,例如图中的1号点,它的left指向NULL,那么下界就相应变为0;right指向NULL,上界就相应变为n-1。后面确定左右儿子的操作和之前一样。读完vector中的所有节点后,循环结束。 最后要注意的是,到此为止所有TreeNode的val值都是序号,因此还要再遍历一次把它们都改为实际的元素值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return NULL;

        vector<TreeNode*> nodeList;
        vector<TreeNode*>::iterator it;
		int mid = n/2;
		int lb, ub, leftIndex, rightIndex;
		
		TreeNode* root = new TreeNode(mid);
		TreeNode* cur;
		nodeList.push_back(root);
		int i = 0;

		while(i<n) {
			cur = nodeList[i];
			lb = 0;
			ub = n-1;
			if(cur->right != NULL) {
				ub = cur->right->val-1;
			}
			if(cur->left != NULL) {
				lb = cur->left->val+1;
			}
		
			mid = cur->val;
			leftIndex = (mid+lb)/2;
			rightIndex = (mid+ub+2)/2;

			if(leftIndex<mid && leftIndex>=lb) {
				TreeNode* left = new TreeNode(leftIndex);
				left->right = cur;
				left->left = cur->left;
				cur->left = left;
				nodeList.push_back(cur->left);
			}
			else cur->left = NULL;
			if(rightIndex>mid && rightIndex<=ub) {
		    	TreeNode* right = new TreeNode(rightIndex);
		    	right->left = cur;
		    	right->right = cur->right;
	        	cur->right = right;
    			nodeList.push_back(cur->right);
    		}
    		else cur->right = NULL;

			++i;
		}
		
		for(it=nodeList.begin(); it!=nodeList.end(); ++it) {
		    cur = *it;
		    cur->val = nums[cur->val];
		}
		return root;
    }
};

© 著作权归作者所有

共有 人打赏支持
cofama
粉丝 0
博文 22
码字总数 19162
作品 0
广州
程序员
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder ⋅ 2017/09/10 ⋅ 0

Leetcode日记5

(2015/11/18) LeetCode 96 Unique Binary Search Trees:(Medium) 1)若用95题的方法递归就会超时。 2)参考《算法导论》第15章,采用自底向上的方法实现动态规划算法。 题目: Given n,...

fxdhdu ⋅ 2015/11/18 ⋅ 0

决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 01/25 ⋅ 0

搜索引擎中的倒排索引(inverted index)机制

Abstract This chapter presents a survey of the various structures (techniques) that can be used in building inverted files, and gives the details for producing an inverted file ......

GarfieldEr007 ⋅ 2016/01/07 ⋅ 0

Leetcode108——Convert Sorted Array to Binary Search Tree

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 2. 求解 这个题主要......

Quincuntial ⋅ 2017/03/23 ⋅ 0

决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 02/09 ⋅ 0

leetcode算法题解(Java版)-15-动态规划(斐波那契)

一、二叉树遍历 题目描述 Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth ......

kissjz ⋅ 05/21 ⋅ 0

浅谈二分查找

定义 In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value ......

云胡_ ⋅ 2017/11/26 ⋅ 0

LeetCode日记3

(2015/11/3) LeetCode-36 Valid Sudoku:(easy) 1)使用数据结构 set<char> emptyset; vector<set<char>> mp(27, emptyset); 2)下标0-8存储行中的数字,9-17存储列中的数字,18-26存储3......

fxdhdu ⋅ 2015/11/13 ⋅ 0

140个Google面试问题

原文地址:http://www.cnblogs.com/hanyulcf/archive/2010/12/03/1895934.html 某猎头收集了140多个Google的面试题,都张到他的Blog中了,主要是下面这些职位的,因为被墙,且无任何敏感信息...

迷途d书童 ⋅ 2012/03/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 8分钟前 ⋅ 0

Cube、Cuboid 和 Cube Segment

1.Cube (或Data Cube),即数据立方体,是一种常用于数据分析与索引的技术;它可以对原始数据建立多维度索引。通过 Cube 对数据进行分析,可以大大加快数据的查询效率 2.Cuboid 在 Kylin 中特...

无精疯 ⋅ 46分钟前 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 48分钟前 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 59分钟前 ⋅ 0

云计算的选择悖论如何对待?

人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云计算为...

linux-tao ⋅ 今天 ⋅ 0

Redis 注册为 Windows 服务

Redis 注册为 Windows 服务 redis 注册为 windows 服务相关命令 注册服务 redis-server.exe –service-install redis.windows.conf 删除服务 redis-server –service-uninstall 启动服务 re......

Os_yxguang ⋅ 今天 ⋅ 0

世界那么大,语言那么多,为什么选择Micropython,它的优势在哪?

最近国内MicroPython风靡程序界,是什么原因导致它这么火呢?是因为他功能强大,遵循Mit协议开源么? 错!因为使用它真的是太舒服了!!! Micropython的由来,这得益于Damien George这位伟大...

bodasisiter ⋅ 今天 ⋅ 0

docker 清理总结

杀死所有正在运行的容器 docker kill $(docker ps -a -q) 删除所有已经停止的容器(docker rm没有加-f参数,运行中的容器不会删掉) docker rm $(docker ps -a -q) 删除所有未打 dangling 标...

vvx1024 ⋅ 今天 ⋅ 0

关于学习

以前学车的时候,教练说了这样的一句话:如果一个人坐在车上一直学,一直学,反而不如大家轮流着学。因为一个人一直学,就没有给自己留空间来反思和改进。而轮流着学的时候大家下来之后思考上...

mskk ⋅ 今天 ⋅ 0

压缩工具之gzip-bzip2-xz

win下常见压缩工具:rar zip 7z linux下常见压缩工具:zip gz bz2 xz tar.gz tar.bz2 tar.xz gzip 不支持目录压缩 gzip 1.txt #压缩。执行后1.txt消失,生成1.txt.gz压缩文件 gzip -d 1.txt....

ZHENG-JY ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部