[Java] Daily LeetCode Challenge 109. Convert Sorted List to Binary Search Tree

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

Convert Sorted List to Binary Search Tree - LeetCode

 

문제 해석

• LinkedList의 중간을 Root로 설정
• Left = 처음~root 이전까지 연결된 LinkedList의 중간점
• Right = root 이후 ~ 끝까지 연결된 LinkedList의 중간점

이런식으로 이진트리를 완성해나가면 된다

 

 

그림으로 설명하면 아래와 같음

 

 

어차피 ListNode에서는 val값만 필요해서 추출후 ArrayList에 값 할당 후 이용해주었고,

중간점 찾아서 루트로 만들어주는 함수 만들어서 재귀 호출 방식으로 트리를 완성해주었다

 

 

[코드]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * 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 ArrayList<Integer> allArr = new ArrayList<>();
    public TreeNode sortedListToBST(ListNode head) {
        setTreeArr(head);
        TreeNode tn = setTree(0, allArr.size()-1);

        return tn;
    }

    public TreeNode setTree(int start, int end){
        if(start > end)
            return null;

        TreeNode tn = new TreeNode();

        int mid = (start+end)%2==0? (start+end)/2 : (start+end)/2+1;
        tn.val = allArr.get(mid);
        tn.left = setTree(start, mid-1);
        tn.right = setTree(mid+1, end);

        return tn;
    }

    public void setTreeArr(ListNode node){
        while(node != null){
            allArr.add(node.val);
            node = node.next;
        }
    }
}