文档章节

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 108. Convert Sorted Array to Binary Search Tree

题目链接 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/ 题目描述 Given an array where elements are sorted in ascending order, convert it ......

xgnming
08/28
0
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
数组->二叉树 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
搜索引擎中的倒排索引(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

没有更多内容

加载失败,请刷新页面

加载更多

RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
48分钟前
6
0

中国龙-扬科
昨天
2
0
Linux系统设置全局的默认网络代理

更改全局配置文件/etc/profile all_proxy="all_proxy=socks://rahowviahva.ml:80/"ftp_proxy="ftp_proxy=http://rahowviahva.ml:80/"http_proxy="http_proxy=http://rahowviahva.ml:80/"......

临江仙卜算子
昨天
9
0
java框架学习日志-6(bean作用域和自动装配)

本章补充bean的作用域和自动装配 bean作用域 之前提到可以用scope来设置单例模式 <bean id="type" class="cn.dota2.tpye.Type" scope="singleton"></bean> 除此之外还有几种用法 singleton:......

白话
昨天
8
0
在PC上测试移动端网站和模拟手机浏览器的5大方法

总结很全面,保存下来以备不时之需。原文地址:https://www.cnblogs.com/coolfeng/p/4708942.html

kitty1116
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部