[LeetCode#] Invert Binary Tree

 

❒ Description

---

날짜	2024.09.22 (토)
레벨	Easy
제목	Invert Binary Tree
링크	https://leetcode.com/problems/invert-binary-tree/
자료구조	그래프
알고리즘	X
시간 복잡도	O(n)

 

이번 문제는 재귀구조를 연습할 수 있는 좋은 문제였다. 다양한 풀이 방법을 통해 재귀에 익숙해지자.

 

 

 

 

 

❒ Solution

---

1. 새로운 노드 생성 DFS

public invertTree(TreeNode root) {
    if (root == null) return null;
    
    // 1. 새로운 노드 생성
    TreeNode inverted = new TreeNod(root.val);
    
    // 2. 새로운 노드의 left, right 설정
    inverted.left = invert(root.right);
    inverted.right = invert(root.left);
    
    // 3. 새로운 노드 반환
    return inverted;
}

 

 

2. 일반 재귀구조 DFS

public TreeNode invertTree(TreeNode root) {
    if (root != null) {
        // 임시 변수(temp)를 사용해서 좌우 교체
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
		
        invertTree(root.left); // 왼쪽 자식 노드 DFS
        invertTree(root.right);// 오른쪽 자식 노드 DFS 
    }
    return root;
}

 

 

3. 후위 순위 재귀구조 DFS

public TreeNode invertTree(TreeNode root) {
    if (root != null) {		
        invertTree(root.left);
        invertTree(root.right);

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
    return root;
}

 

 

4. 반복구조 DFS

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        if (node.hasLeft()) {
            stack.push(node.left);
        }
        if (node.hasRight() {
            stack.push(node.right);
        }
    }
    return root;
}

 

 

5. 반복구조 BFS

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while (!q.isEmpty()) {
        TreeNode node = q.remove();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        if (node.hasLeft()) {
            q.offer(node.left);
        }
        if (node.hasRight() {
            q.offer(node.right);
        }
    }
    return root;
}

 

 

 

 

 

 

---