[코테연습] 2415. Reverse Odd Levels of Binary Tree

오늘은 깊이너비 탐색 - 이진트리 문제가 주어졌다.

이 문제는 홀수인 node 의 값을 완전히 반대로하여 거꾸로 트리의 루트 값 ( root.val ) 을 변경하는 문제였다.

즉, root 탐색을 하다가 홀수 레벨의 root 의 value 를 역순으로 재생시키는 것이다.


Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]

라는 숫자가 있다면,

1 Level 의 1 과 2를 거꾸로 하여 => 2,1 으로
3 Level 의 1,1,1,1,2,2,2,2 를 거꾸로하여 => 2,2,2,2,1,1,1,1 으로.

root 의 변경없이 값만 변경하는 것이다.

문제파악에도 시간이 걸렸지만 root 의 left 와 right 를 변경하지 않고 value 값만 변경한다는게 

여간 까다로웠다.

내가 생각한 논리는 다음과 같다.

1. root 를 탐색한다
2. 홀수 level 의 root 의 value 를 Map<Integer,Stack<Integer>> 리스트에 담는다.
3. 다시 root 를 탐색한다
4. root 가 홀수 level 일 경우, depth를 key 로한 stack 에서 root.val 값을 하나씩 다시 주입한다.

 

class Solution {
    Map<Integer, Stack<Integer>> map = new HashMap<>();
    public TreeNode reverseOddLevels(TreeNode root) {
        findNode(root,0);

        System.out.println(map);

        changeNode(root, 0);
        return root;
    }
    void findNode(TreeNode root, int depth) {

        if (root == null) {
            return;
        }
        Stack<Integer> stack = new Stack<>();
        if (map.get(depth) != null) {
            stack = map.get(depth);
        }
        stack.add(root.val);
        map.put(depth, stack);

        findNode(root.left, depth+1);
        findNode(root.right, depth+1);

    }
    void changeNode(TreeNode root, int depth){
        if(root == null) {
            return;
        }
        if (depth % 2 != 0) {
            Stack<Integer> stack = map.get(depth);
            root.val = stack.pop();
        }
        changeNode(root.left, depth+1);
        changeNode(root.right, depth+1);
    }
}

 

.. 해당 방법으로 하면 당연히 비효율적일 것을 알았으나 1시간 내에 다른 아이디어가 떠오르지 않아, 코딩을 마무리했다.

다른 개발자의 정답이 궁금하여 찾아보았다.

다른 개발자들은 Queue 를 사용하여 BFS 방법으로 풀거나, dfs 로 탐색하면서 배열 요소를 변경하는 것 처럼 해결한것 을 보았다.

인상적이었던 다른 개발자의 코드를 소개한다.

 

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/solutions/3596714/2415-reverse-odd-levels-of-binary-tree-java/

 

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if(root==null)
            return root;
        dfs(root.left,root.right,1);
        return root;
    }
    public void dfs(TreeNode node1,TreeNode node2,int lev)
    {
        if(node1==null||node2==null)
            return ;
        if(lev%2==1)
        {
            int help=node1.val;
            node1.val=node2.val;
            node2.val=help;
        }
        dfs(node1.left,node2.right,lev+1);              
        dfs(node2.left,node1.right,lev+1);
        
    }
}