[LeetCode] 1382. Balance a Binary Search Tree

https://leetcode.com/problems/balance-a-binary-search-tree/description/

leetcode - Balance a Binary Search Tree

문제 유형 : 트리, 재귀, 이진트리, 이진탐색트리

문제 난이도 : Medium

 

문제

Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.

A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

 

이진탐색트리의 루트가 주어진다.

균형을 잡아서 반환하시오.

이진트리의 양쪽 서브트리 깊이의 차이가 1 이하인 경우에 균형잡혔다고 합니다.

 

풀이

중위 순회로 배열에 요소를 정렬된 채로 넣는다.

 

배열을 이용하여 새로 이진탐색트리를 만들어주면 된다.

처음에 left = 0, right = n-1로 시작한다.

현재 서브트리의 루트의 값은 left와 right의 중앙인덱스값인 mid,

양쪽 자식은[left, mid-1], [mid+1, right]의 범위로 하위 서브트리를 만든다.

이렇게 하면 균형잡힌 이진트리를 새로 만들 수 있다.

 

코드

C++

/**
 * 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 {
private:
    vector<int> arr;
public:
    void inorder(TreeNode* root) {
        if(root == NULL) return;
        inorder(root -> left);
        arr.push_back(root -> val);
        inorder(root -> right);
    }

    TreeNode* generate(int left, int right) {
        if(left > right) return NULL;
        int mid = (left + right)/2;
        TreeNode* leftNode = (left > mid-1)? NULL:generate(left, mid-1);
        TreeNode* rightNode = (mid+1 > right)? NULL:generate(mid+1, right);
        return new TreeNode(arr[mid], leftNode, rightNode);
    }

    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return generate(0, arr.size()-1);
    }
};