LeetCode 108. Convert Sorted Array to Binary Search Tree

LeetCode 108. Convert Sorted Array to Binary Search Tree

Description:

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

     0
    / \
  -3   9
  /   /
-10  5

---

分析：

二叉搜索树，即二叉排序树，左子树结点的值都比根节点小，右子树结点的值都比根节点大。

首先判断数组大小，若大小为0，则返回NULL；若大小为1，则该数为根节点，返回new TreeNode(nums[0]).

此题已经是排序后的数组，我们把数组中间的数作为根节点，然后以该中间数分割数组成左右两个数组，再递归分析这两个数组。

代码如下：

#include <iostream>
#include <vector>
using namespace std;
/**
 * 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) {
		if (nums.size() == 0) return NULL;
		if (nums.size() == 1) return new TreeNode(nums[0]);
		// 根节点
		int middle = nums.size() / 2;
		TreeNode* root = new TreeNode(nums[middle]);
		// 左子树/右子树
		vector<int> leftVectors(nums.begin(), nums.begin() + middle);
		vector<int> rightVectors(nums.begin() + middle + 1, nums.end());
		// 递归
		root->left = sortedArrayToBST(leftVectors);
		root->right = sortedArrayToBST(rightVectors);
		return root;
	}
};
void preorder(TreeNode* root) {
	if (root == NULL) cout << "null" << " ";
	else {
		cout << root->val << " ";
		preorder(root->left);
		preorder(root->right);
	}
}
int main() {
	Solution s;
	vector<int> nums;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		nums.push_back(num);
	}
	TreeNode* root = s.sortedArrayToBST(nums);
	preorder(root);
	return 0;
}