LeetCode 2415. Reverse Odd Levels of Binary Tree(JAVA)

출처 : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/?envType=daily-question&envId=2024-12-20

 

#문제

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.


완전 이진 트리(perfect binary tree)의 루트 노드가 주어졌을 때, 트리의 홀수 레벨에 있는 노드 값들을 뒤집어야 합니다.예를 들어, 레벨 3의 노드 값들이 [2, 1, 3, 4, 7, 11, 29, 18]이라면, 이것을 [18, 29, 11, 7, 4, 3, 1, 2]로 바꿔야 합니다.이 과정을 수행한 트리의 루트를 반환하세요.
완전 이진 트리란 모든 부모 노드가 두 자식을 가지고 있고 모든 리프(leaf) 노드가 같은 레벨에 위치한 트리를 의미합니다.여기서 노드의 레벨(level)이란 루트 노드와의 경로에서 존재하는 간선의 개수를 의미합니다.

/**
 * 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;
 *     }
 * }
 */

 

접근1. BFS

BFS탐색을 통해 뒤집어야할 숫자를 기억한 뒤  홀수 레벨에 해당하는 노드들의 값을 바꿔주는 방식으로 문제를 해결

public TreeNode reverseOddLevels(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    
    //뒤집어야하는 숫자들
    int[] nums = {root.val};
    int depth = 0;
    int index;
    while(!queue.isEmpty()) {
        int size = queue.size();
        //현재 짝수레벨이라면 자식노드들은 홀수레벨이므로 완전이진탐색의 특성상 size*2의 공간이 필요함 
        if((depth & 1) ==0) nums = new int[size*2];
        index = 0;
        for(int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            if((depth&1) == 1) {
                //현재 홀수레벨이라면저장된 값들을 역순으로 할당해준다
                cur.val = nums[nums.length-1-i];
            }
            if(cur.left == null || cur.right == null) continue;
            queue.add(cur.left);
            queue.add(cur.right);
            
            //현재 짝수레벨이라면 자식노드들의 값을 저장 
            if((depth & 1) ==0){
                nums[index++] = cur.left.val;
                nums[index++] = cur.right.val;
            }
        }
        //레벨 증가
        depth++;
    }

    return root;
}

 

 

접근2. DFS

DFS 탐색을 통해 대칭 위치에 있는 두 노드(left 노드와 right 노드)를 동시에 탐색하여 부모 노드를 기준으로 대칭인 두 자식 노드의 값을 서로 교환하는 방식으로 문제를 해결

 

public TreeNode reverseOddLevels2(TreeNode root) {
    dfs(root.left,root.right,1);
    return root;
}
//left.left <==> right.right , left.right <==> right.left 
public void dfs(TreeNode left,TreeNode right,int depth) {
    if(left == null && right == null) return;
    //레벨이 홀수라면 두 노드의 값을 바꿔준다
    if((depth & 1) == 1){
        int t = left.val;
        left.val = right.val;
        right.val = t;
    }
    
    //현재 노드를 중심으로 왼쪽, 오른쪽 노드를 동시에 탐색
    //탐색의 기준이 left,right 각각의 노드에서 진행함에 유의해야함
    dfs(left.left,right.right,depth+1);
    
    dfs(left.right,right.left,depth+1);
}