文档章节

108. Convert Sorted Array to Binary Search Tree

cofama
 cofama
发布于 2017/02/27 22:42
字数 862
阅读 1
收藏 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
博文 24
码字总数 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
0
决战Leetcode: easy part(1-50)

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

qq_32690999
01/25
0
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
0
数组->二叉树 Convert Sorted Array to Binary Search Tree

问题: Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary t......

叶枫啦啦
2017/08/11
0
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
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 种族不同,禁止交往

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小小编辑:推荐歌曲《苏菲小姐》- 鱼果 《苏菲小姐》- 鱼果 手机党少年们想听歌,请使劲儿戳(这里) @貓夏:下大雨 正是睡觉的好时候 临睡前...

小小编辑
今天
183
6
Python 搭建简单服务器

Python动态服务器网页(需要使用WSGI接口),基本实现步骤如下: 1.等待客户端的链接,服务器会收到一个http协议的请求数据报 2.利用正则表达式对这个请求数据报进行解析(请求方式、提取出文...

代码打碟手
今天
1
0
Confluence 6 删除垃圾内容

属性(profile)垃圾 属性垃圾的定义为,一个垃圾用户在 Confluence 创建了用户,但是这个用户在自己的属性页面中添加了垃圾 URL。 如果你有很多垃圾用户在你的系统中创建了属性,你可以使用...

honeymose
今天
0
0
qduoj~前端~二次开发~打包docker镜像并上传到阿里云容器镜像仓库

上一篇文章https://my.oschina.net/finchxu/blog/1930017记录了怎么在本地修改前端,现在我要把我的修改添加到部署到本地的前端的docker容器中,然后打包这个容器成为一个本地镜像,然后把这...

虚拟世界的懒猫
今天
1
0
UML中 的各种符号含义

Class Notation A class notation consists of three parts: Class Name The name of the class appears in the first partition. Class Attributes Attributes are shown in the second par......

hutaishi
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部