매일 열리는 코드 챌린지 난이도가 medium이었다. 덕분에 첫 medium 난이도를 풀어보게 되었다.
주어진 int[] array의 숫자들을 Tree에 담아서 리턴을 해야하는데, 이 때 주어진 숫자들은 전위순회를 한 형태의 array로 주어진다.
결과값인 Tree의 형태는 Binary Search Tree여야 한다.
Input/Output 예시는 아래와 같다.
Input : [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Tree의 형태는 이전 포스트에서 가장 긴 경로를 찾는 TreeNode와 동일한 형태의 클래스이다.
recursion 형태의 코드로 BST를 만들도록 코드를 작성하였다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root =null;
for(int i = 0; i < preorder.length; i++) {
root = insertValues(preorder[i], root);
}
return root;
}
public TreeNode insertValues(int val, TreeNode node) {
if(node==null) {
return new TreeNode(val);
}
if(node.val > val){
node.left = insertValues(val, node.left);
} else {
node.right = insertValues(val, node.right);
}
return node;
}
}