티스토리 뷰

반응형

문제

https://leetcode.com/problems/create-binary-tree-from-descriptions/description/

 

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

풀이 코드

/**
 * 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 {
    /**
     * 배열을 탐색 하면서 TreeNode를 만들고, 
     *      키가 node.val이고 값이 TreeNode인 map에 담는다.
     *      자식 val은 set에 담아 둔다.
     * 자식 val을 담은 set에 포함되지 않은 map의 키의 값을 return. 
     */
    public TreeNode createBinaryTree(int[][] descriptions) {
        // node.val이 key, TreeNode가 value인 map을 초기화한다.
        HashMap<Integer, TreeNode> map = new HashMap<>();
        // 자식 node.val을 담을 set을 초기화한다.
        HashSet<Integer> set = new HashSet<>();

        for (int[] description : descriptions) {
            int parent = description[0];
            int child = description[1];
            int isLeft = description[2];

            // map에 없으면 넣어준다.
            if (!map.containsKey(parent)) {
                map.put(parent, new TreeNode(parent));
            }
            if (!map.containsKey(child)) {
                map.put(child, new TreeNode(child));
            }

            // map에 넣은 TreeNode에 자식 노드를 넣어준다.
            TreeNode node = map.get(parent);
            if (isLeft == 1) {
                node.left = map.get(child);
            } else {
                node.right = map.get(child);
            }

            // root를 알기 위해 자식 node를 set에 담아둔다.
            set.add(child);
        }

        for (int nodeVal : map.keySet()) {
            // set에 없으면 root이다.
            if (!set.contains(nodeVal)) {
                return map.get(nodeVal);
            }
        }
        return null;
    }
}
반응형

'코딩테스트 > LeetCode' 카테고리의 다른 글

Max Area of Island  (0) 2023.10.12
Keys and Rooms  (0) 2023.10.12
Symmetric Tree  (0) 2023.10.10
Two Sum IV - Input is a BST  (0) 2023.10.10
Count Good Nodes in Binary Tree  (0) 2023.10.06
반응형