文档章节

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
搜索引擎中的倒排索引(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

没有更多内容

加载失败,请刷新页面

加载更多

deepin系统使用deepin-wine安装exe程序

deepin自带原生deepin-wine使用命令如下: deepin-wine QQBrowser.exedeepin-wine QQMusicSetup.exe 默认安装的快捷方式位置: /root/.wine/drive_c/'Program Files'/Tencent/QQBrowser/......

临江仙卜算子
45分钟前
2
0
快速get到学习Linux操作系统的点

快速get到学习Linux操作系统的点 Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。Linux能够运行主要的UNIX工具软件...

linuxCool
52分钟前
3
0
聊聊:Linux分区的那些方案

安装linux的整体步骤其实比较简单,唯一可能值得说明的地方,大概就是linux的分区了。 下面来给大家推荐一些分区方案。 1 分两个区 实际上,很多时候我们只需要分两个区:`/`和交换分区,日常...

Linux就该这么学
今天
1
0
适配器模式和外观模式

适配器模式: 将一个类的接口,转换成客户期望的另一个接口。适配器让原本不兼容的类可以合作无间。 例子: //将Enumeration转换成Iteratorpublic class EnumerationIterator implements Iter...

王怀楼
今天
4
0
7-CXF与Spring整合发布webservice

Spring+CXF整合来管理webservice 实现步骤: 1. 添加cxf.jar 包(集成了Spring.jar、servlet.jar ),spring.jar包 ,servlet.jar 包 2. 编写业务类,通过CXF来发布webservice 员工管理: 方法...

江戸川
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部