列表

详情


NC11. 将升序数组转化为平衡二叉搜索树

描述

给定一个升序排序的数组,将其转化为平衡二叉搜索树(BST).

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值,右子树中所有节点的值都大于 node 的值,并且左右子树的节点数量之差不大于1

数据范围:,数组中每个值满足
进阶:空间复杂度 ,时间复杂度

例如当输入的升序数组为[-1,0,1,2]时,转化后的平衡二叉搜索树(BST)可以为{1,0,2,-1},如下图所示:
或为{0,-1,1,#,#,#,2},如下图所示:
返回任意一种即可。

示例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;
    }
};

上一题