将升序数组转化为bst

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

http://www.nowcoder.com/questionTerminal/7e5b00f94b254da599a9472fe5ab283d

/**
 * 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
        if (num.size() == 0) {
            return nullptr;
        }
        return createBST(num, 0, num.size() - 1);
    }

    TreeNode* createBST(vector<int>& num, int left, int right) {

        if (left > right) {
            return nullptr;
        }
        // left + (right - left) / 2和left + (right - left + 1) / 2 区别在于是左子树深些还
        // 是右子树深些
        int mid = left + (right - left + 1) / 2;
        TreeNode* root = new TreeNode(num[mid]);
        root->left = createBST(num, left, mid - 1);
        root->right = createBST(num, mid + 1, right);

        return root;
    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务