[leetcode 108] 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:

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

 

 

 

 

 

 

문제 풀이:

이전에 풀었던 문제와 유사하다. 배열을 보고 bst로 변환시키는 문제이다. 

이번엔 오름차순 배열이다. bst는 루트를 기준으로 왼쪽 서브트리 < 루트, 루트 < 오른쪽 서브트리 이기 때문에 배열 중간에 있는 값이 루트노드가 된다.

그리고 루트를 중심으로 나뉜 왼쪽배열과 오른쪽 배열을 기준으로 다시 서브트리를 각각 만들어준다. (재귀)

eazymean.tistory.com/119

[leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    TreeNode* buildBST(vector<int>& nums, int start, int end){
        if(start > end){
            return nullptr;
        }
        
        int mid = start + (end - start)/2;
        int rootVal = nums[mid];
        
        TreeNode* root = new TreeNode(rootVal);
        
        root->left = buildBST(nums, start, mid-1);
        root->right = buildBST(nums, mid+1, end);
        return root;
                           
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int len = nums.size();
        
        return buildBST(nums, 0, len-1);
    }
};