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

 

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

 

 

 

1. 문제 및 접근

 

2415 Reverse Odd Levels of Binary Tree

 

binaryTree, 완전이진탐색트리인듯 (홀수 level의 경우만 reverse)

2 ~ 2^14(16,384) , levels 수 0 ~ 10^5

k level의 노드들은 2^k-1 만큼의 노드를 가지고, 총 n개의 노드를 가진다면 log2(n+1)의 level을 가짐

그러면 list에 저장된 level을 파악 후 홀수 여부 판별 -> 왼 오 교환 하는 형태로 재귀 호출

 

홀수인 level의 노드를 바꿔라 ! dfs로 레벨을 늘려가며, 홀수의 level일 경우 swap 해줘야겠다.

 

제한 사항

 

The number of nodes in the tree is in the range [1, 214].

0 <= Node.val <= 105

root is a perfect binary tree.

 

 

 

 

 

 

 

2. 풀이

 

 

ublic TreeNode reverseOddLevels(TreeNode root) {

        if (root == null) {

            return root;
        }


        dfs(root.left, root.right, 1);
        return root;

    }

    private void dfs(TreeNode node1, TreeNode node2, int level) {

        if (node1 == null || node2 == null) {
            return;
        }

        if (level % 2 != 0) {
//            swap(node1.val, node2.val);

            int temp = node1.val;
            node1.val = node2.val;
            node2.val = temp;
        }

        dfs(node1.left, node2.right, level + 1);
        dfs(node2.left, node1.right, level + 1);

    }

 

전체 풀이

 

 

 

 

 

2-1 DFS

 

 

 

너무 간단해서 크게 설명할 건 없는데

 

기저조건은null check

 

현재의 level이 홀수라면, node의 지금의 수 val을 서로 교환한다.

 

다음 level로 내려 가려고 +1 후

 

node1.left와 node2.right,  node2.left와 node2.left를 재귀적 호출

 

 

 

 

 

 

3. 마무리

 

 

 

tree 자체가 arr로 입력에 들어가는 leetcode의 방식은 항상 복잡하게 만드는 것 같아서 약간 짜증

 

내가 부족한 탓을 남 탓으로 돌리기.. 웃자고 하는 말이다..

 

재귀적으로 호출하는 과정을 언제쯤이면 머리로 그려질까? 이런 부분은 쉬운 재귀 호출이라 큰일이네