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 tree
struct 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()/;
TreeNode * root = new TreeNode(num[nr]); vector<int> numl(num.begin(), num.begin() + nr);
vector<int> numr(num.begin() + nr + , num.end());
root->left = sortedArrayToBST(numl);
root->right = sortedArrayToBST(numr); return root;
}
}; int main()
{
Solution s;
vector<int> num;
num.push_back();
num.push_back();
num.push_back();
num.push_back();
num.push_back();
num.push_back();
num.push_back(); TreeNode * ans = s.sortedArrayToBST(num); return ;
}