Leet Code - 108. Convert Sorted Array to Binary Search Tree(C++)

예제: Convert Sorted Array to Binary Search Tree

문제
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:

풀이

처음에 어떻게 풀까 고민했었는데, 인풋 데이터도 sorted 데이터고 하니, left와 right로 구분지어서 TreeNode에 하나씩 넣어주면 되겠다 생각 했다. 완전 이진 트리도 아니고, 'possible answer' 단어가 있는 것을 보아, 답이 여러개여도 되겠거니 했는데 그 예상이 적중했다.

말처럼 쉽게 푼 것은 아니지만, 구조체와 포인터에 익숙하다면 위와 같은 로직으로 풀면 되겠다.

전체적인 소스코드는 아래와 같다.

소스 코드

/**
 * 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;

		TreeNode* root = new TreeNode(NULL);
		solve(nums, root, 0, nums.size() - 1);

		return root;
	}

	void solve(vector<int>& nums, TreeNode* node, int left, int right) {

		int mid = (left + right) / 2;
		node->val = nums[mid];

		if (left <= mid - 1) solve(nums, node->left = new TreeNode(NULL), left, mid - 1); //left
		if (right >= mid + 1) solve(nums, node->right = new TreeNode(NULL), mid + 1, right); //right
	}
};

풀이 후기

다른 풀이중에 필자와 비슷한 방식으로 푼 방법이 있었는데, 필자와는 다르게 'solve'함수 부분에서 직접 TreeNode*를 return해주고 있다. 입맛에 맞는 방법을 쓰면 되겠다.(runtime과 memory는 거의 차이가 없었다.)