Reverse Odd Levels of Binary Tree

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

풀이 코드

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        DFS(root.left, root.right, 1);
        return root;
    }

    private static void DFS(TreeNode node1, TreeNode node2, int level) {
        if (node1 == null) {
            return;
        } else {
            if (level % 2 != 0) {
                int temp = node1.val;
                node1.val = node2.val;
                node2.val = temp;
            }
            DFS(node1.left, node2.right, level + 1);
            DFS(node1.right, node2.left, level + 1);
        }
    }
}

입출력 예시

Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation: The tree has only one odd level. The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.

코드 설명

1. root를 기준으로 Binary Tree를 왼쪽과 오른쪽으로 나누어 2개의 Binary Tree라고 생각합니다.
2. 왼쪽 Tree는 전위 순회로 Tree를 순회하고, 오른쪽 Tree는 후위 순회로 Tree를 순회합니다.
3. Tree의 level(Depth)은 DFS method에 parameter로 넘겨서 확인 할 수 있도록 합니다.
4. level이 홀수 일때, 왼쪽 Tree의 node.val과 오른쪽 Tree의 node.val을 서로 바꿔줍니다.
5. DFS method로 Tree의 순회가 끝나면 root를 return 합니다.