NC11. 将升序数组转化为平衡二叉搜索树
描述
示例1
输入:
[-1,0,1,2]
输出:
{1,0,2,-1}
示例2
输入:
[]
输出:
{}
C++ 解法, 执行用时: 2ms, 内存消耗: 336KB, 提交时间: 2021-06-06
class Solution { public: TreeNode *sortedArrayToBST(vector<int> &num) { return ArrayToBST(num,0,num.size()); } TreeNode *ArrayToBST(vector<int> &num,int begin,int end) { if(begin >= end) return nullptr; int middle = begin+(end-begin)/2; TreeNode *root = new TreeNode(num[middle]); root->left = ArrayToBST(num,begin,middle); root->right = ArrayToBST(num,middle+1,end); return root; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 336KB, 提交时间: 2021-03-02
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param num int整型vector * @return TreeNode类 */ //二叉搜索树:对于一个节点,其左孩子的值小鱼该节点的值,右孩子的值大于该节点的值 // 对于一颗二叉树,某节点的左子树和右子树均为平衡二叉树 // 二叉平衡树:空树或左子树和右子树的深度差不超过1 /* 注意一点即可,在求中点的过程中,理论上left + (right-left) / 2和left + (right - left + 1) / 2都是合法的, 但从题目中的示例可以得知,我们的代码里应使用后者才能符合题意。 */ TreeNode* sortedArrayToBST(vector<int>& num) { // write code here if(num.size() < 1) return NULL; TreeNode* root = preOrder(num, 0, num.size() - 1); return root; } TreeNode* preOrder(vector<int>& num, int left, int right) { if(left > right) return nullptr; int mid = left + (right - left + 1) / 2;//找到中间节点,再将左右两边的元素构造成左子树和右子树 TreeNode* root = new TreeNode(num[mid]); // 根节点 root->left = preOrder(num, left, mid - 1); root->right = preOrder(num, mid + 1, right); return root; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2020-12-16
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param num int整型vector * @return TreeNode类 */ TreeNode* sortedArrayToBSTs(vector<int>& num, int s, int e) { if(s >= e) return nullptr; int mid = (s+e)>>1; TreeNode* root = new TreeNode(num[mid]); root->left = sortedArrayToBSTs(num, s, mid); root->right = sortedArrayToBSTs(num, mid+1, e); return root; } TreeNode* sortedArrayToBST(vector<int>& num) { // write code here return sortedArrayToBSTs(num, 0, num.size()); } };
C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-05-04
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param num int整型vector * @return TreeNode类 */ TreeNode* sortedArrayToBST(vector<int>& num) { // write code here return helper(num,0,num.size()-1); } TreeNode* helper(vector<int>&num,int left,int right) { if(left>right) { return NULL; } int mid=(left+right+1)/2; TreeNode*root=new TreeNode(num[mid]); root->left=helper(num,left,mid-1); root->right=helper(num,mid+1,right); return root; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-03-15
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param num int整型vector * @return TreeNode类 */ TreeNode* sortedArrayToBST(vector<int>& num) { // write code here return build(num, 0, num.size()); } TreeNode *build(vector<int> &num, int l, int r) { if (l >= r) return nullptr; int m = (l + r)>>1; TreeNode *tn = new TreeNode(num[m]); tn->left = build(num, l, m); tn->right = build(num, m+1, r); return tn; } };