99클럽 코테 스터디 15일차 TIL + DFS(Reverse Odd Levels of Binary Tree)

오늘의 과제

리트코드 Medium으로 분류된 Reverse Odd Levels of Binary Tree입니다.

 

어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.

문제

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

 

먼저 문제 요구사항 요약입니다.

 

완전한 이진트리(완전 이진트리 아님)가 주어질 때, 홀수 레벨에 있는 노드들의

값을 역순으로 바꿔 반환하면 됩니다.

 

기존 DFS처럼 끝까지 순회하되, 홀수 레벨인지 판별만 해주면 됩니다.

 

사실 값을 서로 바꾸기위해 이전 노드의 값만 기억할 뿐

홀수 여부 체크하는 로직 외에 특별한 코드는 없습니다.

 

단순히 DFS 순회할 때 이전 노드의 Left, Right 값도 같이 인자로 주고

현재 레벨이 홀수라면 서로의 값만 swap해주면 됩니다.

 

 

코드입니다.

/**
 * 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;
 *     }
 * }
 */
import java.util.*;
class Solution {

   public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1);
        return root;
    }

    private void dfs(TreeNode leftNode, TreeNode rightNode, int level) {
        // 포화 이진트리에 왼쪽이 없다면 오른쪽도 없다.
        if (leftNode == null) return;

        // 홀수 판별
        if (level % 2 == 1) {
            // swap
            int tmp = leftNode.val;
            leftNode.val = rightNode.val;
            rightNode.val = tmp;
        }
        dfs(leftNode.left, rightNode.right, level + 1);
        dfs(leftNode.right, rightNode.left, level + 1);
    }
}

배운 점

문제의 풀이에는 금방 접근했으나 TreeNode를 어떻게 반환해야 하는가? 때문에

시간을 많이 허비했습니다.

 

간단히 이미 TreeNode의 주소값을 파라미터로 넘겼으니 바로 파라미터 값을 수정해주면

해결될 일인데 기초 부족이었던 것 같습니다.

 

또한 문제 설명에 완전 이진트리라는 말이 있어 탈출 로직인 leftNode == null도 처음에는 rightNode까지 검사했으나

완전 이진트리가 아닌 완전"한" 이진트리로 포화 이진트리를 말하고 있었습니다.

 

따라서 포화 이진트리에는 왼쪽, 오른쪽 노드가 항상 같이 존재하니 한쪽만 검사해도 나머지 한 쪽에 대한

값이 있는지 여부를 체크할 수 있었습니다.

 

 

오늘의 한줄평

복잡해보이는 문제도 결국은 기본 지식의 모임이다.