99클럽 코테 스터디 13일차 TIL - Binary Tree(이진 트리)

오늘의 학습 키워드

DFS, 이진 트리

---

알고리즘 문제

• LeetCode Medium 2415. Reverse Odd Levels of Binary Tree
• https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/

---

공부한 내용

이진 트리

• 트리 자료 구조
• 각 노드가 최대 2개의 자식 노드(왼쪽, 오른쪽)을 가진다.
• 노드의 Level(레벨)은 루트 노드에서 자신까지 가는 경로의 길이 + 1. 루트 노드 레벨은 1이다.
• 노드의 Depth(깊이)는 루트 노드에서 자신까지 가는 경로의 길이. 루트 노드 깊이는 0이다. 
• 리프 노드는 자식이 없는 노드를 의미한다.

이진 트리의 대칭 구조와 DFS

• 서로 대칭 구조로 데칼코마니처럼 생각할 수 있다.
• DFS로 재귀 함수 호출 시 같은 레벨의 가장 왼쪽 노드와 가장 오른쪽 노드를 swap하면 대칭적으로 reverse 가능하다.

---

오늘의 회고

처음 시도

• DFS로 처음에 시도를 했는데 이진 트리의 대칭 구조를 활용하지 못하고 해당 노드의 왼쪽, 오른쪽 노드만 swap해서 case 3에서 실패했다. 
• 두번째 시도에서 List<TreeNode> 자료구조를 사용해서 해보려 했는데 DFS와 BFS가 섞인 것 같았다. 

해결

• 이진 트리의 특성을 잘 활용했어야 했고, 다른 사람의 풀이를 듣고 대칭 구조를 활용할 수 있다는 것을 알게 되었다.

---

문제 풀이

/**
 * 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 {
    int tmp;

    public void dfs(TreeNode left, TreeNode right, int depth) {
    	//재귀 종료 조건 => 리프 노드인 경우 (자식 노드가 없는 경우)
        if (left == null && right == null) return;
		
        //depth가 홀수인 경우 left 노드와 right 노드를 swap
        if (depth % 2 == 1) {
            tmp = right.val;
            right.val = left.val;
            left.val = tmp;
        }

		//왼쪽 노드의 왼쪽 자식노드, 오른쪽 노드의 오른쪽 자식 노드 => 중앙 기준으로 바깥쪽의 노드를 swap하도록 세팅
        dfs(left.left, right.right, depth+1);
        //왼쪽 노드의 오른쪽 자식노드, 오른쪽 노드의 왼쪽 자식 노드 => 중앙 기준으로 안쪽의 노드들을 swap하도록 세팅
        dfs(left.right, right.left, depth+1);
    }

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

        return root;
    }
}