欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)

程序员文章站 2022-03-06 10:10:14
1. 题目 1.1 英文题目 Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A hei ......

1. 题目

1.1 英文题目

given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

a height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

1.2 中文题目

给定一个内部元素按照升序排列的数组,请将其转化成高度平衡的二叉搜索树。

1.3输入输出

输入 输出
nums = [-10,-3,0,5,9] [0,-3,9,-10,null,5]
nums = [1,3] [3,1]

1.4 约束条件

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.

2. 实验平台

ide:vs2019
ide版本:16.10.1
语言:c++11

3. 程序

3.1 测试程序

#include "solution.h"
#include <vector>	// std::vector
#include<iostream>	// std::cout
using namespace std;

// 主程序
int main()
{
	// 输入
	vector<int> nums= { -10, -3, 0, 5, 9 };

	solution solution; // 实例化solution
	treenode* output = solution.sortedarraytobst(nums); // 主功能
}

3.2 功能程序

3.2.1 最优算法

(1)代码

#pragma once
#include<vector>    // std::vector
#include<algorithm>
using namespace std;

//definition for a binary tree node.
struct treenode {
    int val;
    treenode* left;
    treenode* right;
    treenode() : val(0), left(nullptr), right(nullptr) {}
    treenode(int x) : val(x), left(nullptr), right(nullptr) {}
    treenode(int x, treenode* left, treenode* right) : val(x), left(left), right(right) {}
    
};
//主功能
class solution {
public:
    treenode* sortedarraytobst(vector<int>& nums) 
    {
        if (nums.size() == 0) return nullptr; // 空数组情况
        int mid = nums.size() / 2; // 定义中点值
        treenode* node = new treenode(nums[mid]);  
        auto lefttree = vector<int>(nums.begin(), nums.begin() + mid); // 左边树结构
        auto righttree = vector<int>(nums.begin() + mid + 1, nums.end()); // 右边树结构
        if (mid != 0) // 左边树结构递归 
            node->left = sortedarraytobst(lefttree); // 递归
        if (mid != nums.size() - 1)
            node->right = sortedarraytobst(righttree);
        return node;
    }
};

参考:

(2)解读

参考:

4.其他知识

(1)树

  • 二叉查找树(binary search tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别是二叉排序树。
  • 平衡二叉树(self-balancing binary search tree)又被称为 avl 数,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。

(2)c++结构体

a.作用

最主要的作用就是封装。封装的好处就是可以再次利用。让使用者不必关心这个是什么,只要根据定义使用就可以了。

b.c++中的结构体与类的区别

class中默认的成员访问权限是private的,而struct中则是public的。 (2)class继承默认是private继承,而从struct继承默认是public继承。

c. c++的结构体可以包含函数,而c的不可以

d. 利用构造函数定义

参考:

e.struct和typedef struct

参考:
参考: