【数组递归构造二叉树】LeetCode 108. Convert Sorted Array to Binary Search Tree

最新推荐文章于 2023-08-14 13:22:55 发布

Allenlzcoder

最新推荐文章于 2023-08-14 13:22:55 发布

阅读量463

点赞数

分类专栏： LeetCode练习题文章标签： LeetCode 108. Convert Sorted A

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/80831720

版权

LeetCode练习题专栏收录该内容

168 篇文章

订阅专栏

本文提供两种将有序数组转换为平衡二叉搜索树的方法。第一种通过递归构造二叉树，第二种则避免了大量复制数组元素，提高了效率。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode 108. Convert Sorted Array to Binary Search Tree

Solution1：我的答案
构造二叉树利用递归

/**
 * 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) {
        return my_sort(nums);
    }

    TreeNode* my_sort(vector<int> nums) {
        if (nums.size() == 0) return NULL;
        else if (nums.size() == 1) {
            TreeNode* root = new TreeNode(nums[0]);
            return root;
        }
        else {
            int root_index = nums.size()/2;
            TreeNode* root = new TreeNode(nums[root_index]);
            vector<int> left_tree, right_tree;
            for (int i = 0; i < nums.size(); i++) {
                if (i < root_index)
                    left_tree.push_back(nums[i]);
                else if (i > root_index)
                    right_tree.push_back(nums[i]);
            }
            root->left = my_sort(left_tree);
            root->right = my_sort(right_tree);
            return root;
        }
    }
};

Solution2：
参考网址：http://www.cnblogs.com/grandyang/p/4295245.html
下面是避免数组元素大量复制的写法，还是这种好啊

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return sortedArrayToBST(num, 0 , num.size() - 1);
    }
    TreeNode *sortedArrayToBST(vector<int> &num, int left, int right) {
        if (left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode *cur = new TreeNode(num[mid]);
        cur->left = sortedArrayToBST(num, left, mid - 1);
        cur->right = sortedArrayToBST(num, mid + 1, right);
        return cur;
    }
};