[LeetCode] 108. Convert Sorted Array to Binary Search Tree

轉自LeetCode

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

<Solution>

這題是要將 sorted array 轉換成 BST

從 BST 的特性可以知道，root 會是在 sorted array 中間的那個數

然後再分成左半部和右半部，分別是左子樹和右子樹

而在 BST 中，左子樹和右子樹也都還會是 BST

所以這題就是一道二分法的題目，只是不是搜尋，而是建 BST 而已

code 如下
c++

	/**
	* 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.empty()) {
	return NULL;
	}
	return recursive(0, nums.size()-1, nums);
	}
	TreeNode *recursive(const int &left, const int &right, vector<int>& nums) {
	if(left > right) {
	return NULL;
	}
	int mid = (left + right) / 2;
	TreeNode *root = new TreeNode(nums[mid]);
	root->left = recursive(left, mid-1, nums);
	root->right = recursive(mid+1, right, nums);
	return root;
	}
	};

view raw sortedArrayToBinarySearchTree_1.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun sortedArrayToBST(nums: IntArray): TreeNode? {
	return build(0, nums.lastIndex, nums)
	}
	fun build(left: Int, right: Int, nums: IntArray): TreeNode? {
	if (left > right) {
	return null
	}
	val mid = left + (right - left) / 2
	val root = TreeNode(nums[mid])
	root.left = build(left, mid-1, nums)
	root.right = build(mid+1, right, nums)
	return root
	}
	}

view raw convert_sorted_array_to_binary_search_tree.kt hosted with ❤ by GitHub

還有 iterative 的做法 (參考資料)

想法如下

• 一樣是使用二分法的概念，只是用一個 queue 將 left index 和 right index 存起來，然後依序處理

• 配合上面步驟存的 index，也用一個 queue 將對應的 node 存起來

• 根據 left index 和 right index，把對應的值給對應的 node

code 如下

	/**
	* 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.empty()) {
	return NULL;
	}
	//> the value is only dummy value
	TreeNode *root = new TreeNode(0);
	queue<TreeNode *> nodeQue;
	nodeQue.push(root);
	//> left index and right index of nums
	queue<pair<int, int>> indexQue;
	indexQue.push({0, nums.size()-1});
	while(!nodeQue.empty()) {
	//> get left and right indices
	int left = indexQue.front().first;
	int right = indexQue.front().second;
	indexQue.pop();
	TreeNode *currNode = nodeQue.front();
	nodeQue.pop();
	//> update node's value according to left and right indices
	int mid = (left + right) / 2;
	currNode->val = nums[mid];
	if(left <= (mid-1)) {
	currNode->left = new TreeNode(0); //> the value is only dummy value
	nodeQue.push(currNode->left);
	indexQue.push({left,mid-1});
	}
	if((mid+1) <= right) {
	currNode->right = new TreeNode(0); //> the value is only dummy value
	nodeQue.push(currNode->right);
	indexQue.push({mid+1,right});
	}
	}
	return root;
	}
	};

view raw sortedArrayToBinarySearchTree_2.cpp hosted with ❤ by GitHub

可以使用 C++11 引入的 tuple 來改寫 iterative 的解法，這樣就不需要兩個 queue 了

code 如下

	/**
	* 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.empty()) {
	return NULL;
	}
	TreeNode *root = new TreeNode(0); //> the value is only dummy value
	queue<tuple<int, int, TreeNode *>> nodeQue;
	nodeQue.push(make_tuple(0, nums.size()-1, root));
	while(!nodeQue.empty()) {
	int left, right;
	TreeNode *currNode;
	tie(left, right, currNode) = nodeQue.front();
	nodeQue.pop();
	if(left > right) {
	continue;
	}
	//> update node's value according to left and right indices
	int mid = (left + right) / 2;
	currNode->val = nums[mid];
	if(left <= (mid-1)) {
	currNode->left = new TreeNode(0); //> the value is only dummy value
	nodeQue.push(make_tuple(left, mid-1, currNode->left));
	}
	if((mid+1) <= right) {
	currNode->right = new TreeNode(0); //> the value is only dummy value
	nodeQue.push(make_tuple(mid+1, right, currNode->right));
	}
	}
	return root;
	}
	};

view raw sortedArrayToBinarySearchTree_3.cpp hosted with ❤ by GitHub