108. Convert Sorted Array to Binary Search Tree
博客专区 > cofama 的博客 > 博客详情
108. Convert Sorted Array to Binary Search Tree
cofama 发表于10个月前
108. Convert Sorted Array to Binary Search Tree
  • 发表于 10个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

原题连接 > 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;
    }
};
共有 人打赏支持
粉丝 0
博文 22
码字总数 19162
×
cofama
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: