99클럽 코테 스터디 15일자 TIL + reverse-odd-levels-of-binary-tree

이월(0216tw)·2024년 6월 3일

99클럽 TIL 개발자 취업 기능개발 미들러 자바 정렬 코딩테스트 코딩테스트준비 항해99

99클럽/알고리즘풀이

목록 보기

17/38

문제 출처

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree (leetcode)

학습 키워드

DFS/BFS

시도 방법

DFS 사용해 재귀적으로 풀이

내가 작성한 코드 (외부 도움 받음)

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {

        dfs(0 , root.left , root.right); 
        return root; 
    }

    public void dfs(int depth , TreeNode node1 , TreeNode node2) {
        
        if(node1 == null || node2 == null) return; 
        
        if(depth % 2 == 0) {  
            int temp = node1.val;        //왼쪽 자식 노드의 값
            node1.val = node2.val; 
            node2.val = temp;    
        }

        //해당 왼쪽, 오른쪽으로 재귀적으로 처리를 진행한다. 
        dfs(depth+1 , node1.left , node2.right); 
        dfs(depth+1 , node1.right, node2.left ); 

    }
}

코드설명

만약 다음과 같이 완전 이진 트리가 있을 때 depth 가 홀수일때만 값을 change 한다.
즉, [2,3] , [8,9,10,11,,,,15] 일 때가 depth가 홀수이다.

그래서 3,2 의 "값만" swap을 하고 중요한 점은 자식노드가 바로 옆의 노드를 swap하는 게 아니라는 것이다.

예를 들어보자.
4 에는 left : 8 , right : 9가 있다.
5 에는 left : 10 , right : 11이 있다.
6 에는 left : 12 , right : 13이 있다.
7 에는 left : 14 , right : 15가 있다.

여기서 4가 노드일때 8,9 가 바뀌는 것이 아니라
4의 left:8 과 7의 right : 15 을 swap 하고
4의 right:9 와 7의 left : 14 를 swap 한다.
5의 left:10 과 6의 right : 13을 swap 하고
4의 right:11과 6의 left:12 를 스왑한다.

결과적으로 15 14 13 12 11 10 9 8 이 된다.
(사실 아직 잘 와닿지는 않는다. 계속 풀어보면서 감을 익혀야겠다.)

Inverse Tree

이 문제의 원 아이디어는 inverse Tree 이다.

노드의 자식노드를 서로 swap 하는 것을 의미하며 코드는 다음과 같이 심플하다.

  public TreeNode reverseOddLevels(TreeNode root) {

        if(root.left != null || root.right != null) {
            TreeNode temp = root.left; 
            root.left = root.right; 
            root.right = temp;  
            //특정 노드의 왼쪽/오른쪽 자식 노드를 변경 
            //(이때 하위 노드들도 함께 이동)

            reverseOddLevels(root.left); 
            reverseOddLevels(root.right); 
        }

        return root; 
    }