[OJ.leetcode] Convert Sorted Array to Binary Search Tree

https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

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

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

/*

balanced definition:

Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.

An empty tree is height-balanced. A non-empty binary tree T is balanced if:

1) Left subtree of T is balanced

2) Right subtree of T is balanced

3) The difference between heights of left subtree and right subtree is not more than 1.

조건:

extra memory : 사용가능

unique? : 당연히 unique

time complexity :O(n)

예제1: [1,2,3,4,5,6,7]

1)right

     4

   /   \

  2     5

  / \  /  \

 1   3 6   7

 

 2)wrong: inefficient

     4

    / \

   3   5

   /    \

  2      6

 /        \

 1         7

 

 3)right

      3

     / \

    2   4

   /   /  \

   1   5   6

           \

            7

     

 

예제2: right

[1,2,3,4,5,6,7,8]

      4

     /  \

    2    6

   /  \ /  \

  1   3 5   7

             \

              8

옳은 접근 방식:

1. balanced 가 되려면 root가 정중앙(짝수인경우 둘중하나) 가 되어야함을 알아채야함

2. 그다음 left는 항상 parent보다 작은값, right는 parent보다 큰 값이 와야하므로 'sorted' 되었다는 힌트를 가지고 중앙값으로부터 양쪽으로

left, right를 만드는 접근이 옳다

3. root 다음값을 선택할때, 배열의 start~root, root~end 사이의 middle 값을 선택해야 하는 것을 눈치채야함. 왜냐하면 root를 선택하는 것과

마찬가지로 root->left의 왼쪽은 root보다 모두 작고, 오른쪽은 모두 root보다 크므로. 오른쪽도 마찬가지

4. 1,2,3을 바탕으로 recursive로 binarysearch를 수행하는 것과 똑같다는 것을 알아챈다면 문제 해결.

*/

/*

첫번째 답: accepted

class Solution {

    public:

    TreeNode * sortedArrayToBST(vector<int> &num) {

        return makeBST(num, 0, num.size()-1);

    }

    

    TreeNode* makeBST(vector<int>& num, int start, int end) {

        if(start > end) return NULL;

        

        if(start <= end) {

            int mid = (start+end)/2;     

            TreeNode* node = new TreeNode(num[mid]);

            node->left = makeBST(num, start, mid-1);

            node->right = makeBST(num, mid+1, end);

            

            return node;

        }

    }

};*/

//두번쨰 시도. 첫번째와 다르게 return 값 대신에 pointer를 인자로 넘겨주어 풀려고 시도. wrong

class Solution {

    public:

    TreeNode * sortedArrayToBST(vector<int> &num) {

        if(num.size() <= 0) {

            return NULL;   

        } else if(num.size() == 1) {

            return new TreeNode(num[0]);    

        }

        

        int mid = (num.size()-1)/2;

        TreeNode * node = new TreeNode(num[mid]);

        makeBST(node, num, 0, num.size()-1);    

            

        return node;

        

    }

    

    void makeBST(TreeNode* node, vector<int>& num, int start, int end) {

            if(start > end) {

                node->left = NULL;

                node->right = NULL;

                

                return;

            }

            

            int mid = (start+end)/2;

            int leftMid = (start+mid-1)/2; 

            int rightMid = (mid+1+end)/2;

            

            if(start > leftMid) {

                node->left = NULL;

            } else {

                TreeNode* left = new TreeNode(num[leftMid]);

                node->left = left;

                

                makeBST(node->left, num, start, mid-1);

            }

            

            if(rightMid > end) {

                node->right = NULL;

            } else {

                TreeNode* right = new TreeNode(num[rightMid]);

                node->right = right;

                

                makeBST(node->right, num, mid+1, end);

            }

        

    }

};