[코테연습] 2196. Create Binary Tree From Descriptions

- TreeNode 문제, HashMap 문제

 

https://leetcode.com/problems/create-binary-tree-from-descriptions/description/?envType=daily-question&envId=2024-07-15

 

 

class Solution {

    /**
        TreeNode 가 없을 경우, map 을 이용해서 생성 여부를 저장한다.
        TreeNode 가 있을 경우, map 에서 꺼내서 left 여부에 따라서 children TreeNode.left / TreeNode.right 에 붙인다.
        붙인 뒤에, map 에 해당 TreeNode를 다시 저장한다.

        해당 반복되었을 경우 TreeNode 에 해당하는 정보값이 모두 map 에저장하게 된다.
        이때, child Node 인지 여부를 확인하기 위해서 Set 에 child Node 정보를 저장한다.
        Child Node 가 아닐 경우 root Node 로 정의하고 해당 값을 return 한다.
     */
    public TreeNode createBinaryTree(int[][] descriptions) {
        
        //TreeNode root 정보를 담을 map
        Map<Integer, TreeNode> map = new HashMap<>();
        //children 여부를 확인할 set
        Set<Integer> childSet = new HashSet<>();
        
        for(int i = 0; i < descriptions.length; i++) {
            int rootVal = descriptions[i][0]; //root value
            int childVal = descriptions[i][1]; //children value
            int left = descriptions[i][2]; //left 여부

            childSet.add(childVal); //child 일 경우에는 해당 value 값을 담는다.

            TreeNode root = map.get(rootVal); // map 에서 root 여부 값을 확인한다.
            if (root == null) { //없을 경우 TreeNode 생성
                root = new TreeNode(rootVal);
            }

            if (left == 1) { // left 여부검사.
                root.left = map.get(childVal); // map 에 있는지 확인한다.
                if (root.left == null) {
                    root.left = new TreeNode(childVal); // 없을 경우 TreeNode 를 생성하고, map 에 저장한다.
                    map.put(childVal, root.left);
                }
            } else {
                root.right = map.get(childVal); 
                if (root.right == null) {
                    root.right = new TreeNode(childVal); 
                    map.put(childVal, root.right);
                }
            }
            map.put(rootVal, root);

        }

        //set 에서 child node 가 아닐 경우 return
        int rootVal = -1;
        for(int i = 0; i < descriptions.length; i++) {
            if (!childSet.contains(descriptions[i][0])) {
                rootVal = descriptions[i][0];
                break;
            }
        }

        return map.get(rootVal);
    }
}