赞
踩
题目链接:108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。
示例 1:
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
这道题要求我们将一个有序的整数数组 nums
,转换为一颗平衡二叉搜索树。本质上就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间。
那么如果数组长度为偶数,中间节点有两个,取哪一个作为分割点呢?
取哪一个都可以,只不过构成了不同的平衡二叉搜索树。
例如:输入:[-10,-3,0,5,9]
如下两棵树,都是这个数组的平衡二叉搜索树:
如果要分割的数组长度为偶数的时候,中间元素为两个,是取左边元素 就是树1,取右边元素就是树2。
这也是题目中强调答案不是唯一的原因。
class Solution { public: TreeNode* traversal(vector<int>& nums, int left, int right) { // 如果左边界大于右边界,则返回空指针 if (left > right) { return nullptr; } // 计算中间位置 int mid = left + ((right - left) >> 1); // 创建根节点,并将中间位置的元素作为根节点的值 TreeNode* root = new TreeNode(nums[mid]); // 递归构建左子树 root->left = traversal(nums, left, mid - 1); // 递归构建右子树 root->right = traversal(nums, mid + 1, right); // 返回根节点 return root; } TreeNode* sortedArrayToBST(vector<int>& nums) { return traversal(nums, 0, nums.size() - 1); } };
迭代法可以通过三个队列来模拟,一个队列放遍历的节点,一个队列放左区间下标,一个队列放右区间下标。模拟的就是不断分割的过程。
主要思路是通过广度优先搜索(BFS)的方式,利用队列来将有序数组转换成一个平衡的二叉搜索树(BST)。
函数的基本步骤如下:
class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if (nums.size() == 0) return nullptr; TreeNode* root = new TreeNode(0); // 初始根节点 queue<TreeNode*> nodeQue; // 放遍历的节点 queue<int> leftQue; // 保存左区间下标 queue<int> rightQue; // 保存右区间下标 nodeQue.push(root); // 根节点入队列 leftQue.push(0); // 0为左区间下标初始位置 rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置 while (!nodeQue.empty()) { TreeNode* curNode = nodeQue.front(); nodeQue.pop(); int left = leftQue.front(); leftQue.pop(); int right = rightQue.front(); rightQue.pop(); int mid = left + ((right - left) / 2); curNode->val = nums[mid]; // 将mid对应的元素给中间节点 if (left <= mid - 1) { // 处理左区间 curNode->left = new TreeNode(0); nodeQue.push(curNode->left); leftQue.push(left); rightQue.push(mid - 1); } if (right >= mid + 1) { // 处理右区间 curNode->right = new TreeNode(0); nodeQue.push(curNode->right); leftQue.push(mid + 1); rightQue.push(right); } } return root; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。