首页 > 代码库 > 【leetcode】Convert Sorted Array to Binary Search Tree (easy)

【leetcode】Convert Sorted Array to Binary Search Tree (easy)

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 

有序数组变二叉平衡搜索树,不难,递归就行。每次先序建立根节点(取最中间的数),然后用子区间划分左右子树。

一次就AC了

 

注意:new 结构体的时候对于

struct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

要用 TreeNode * root = new TreeNode(123);  与构造函数的形式要一致。

#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;//Definition for binary treestruct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    TreeNode *sortedArrayToBST(vector<int> &num) {        if(num.empty())        {            return NULL;        }        int nr = num.size()/2;        TreeNode * root = new TreeNode(num[nr]);        vector<int> numl(num.begin(), num.begin() + nr);        vector<int> numr(num.begin() + nr + 1, num.end());        root->left = sortedArrayToBST(numl);        root->right = sortedArrayToBST(numr);        return root;    }};int main(){    Solution s;    vector<int> num;    num.push_back(1);    num.push_back(2);    num.push_back(3);    num.push_back(4);    num.push_back(5);    num.push_back(6);    num.push_back(7);    TreeNode * ans = s.sortedArrayToBST(num);    return 0;}

 

【leetcode】Convert Sorted Array to Binary Search Tree (easy)