[LeetCode] 226. Invert Binary Tree - 문제풀이

Description

주어진 이진 트리를같은 뎁스의 값들을 뒤집어(invert) 반환하는 문제입니다.

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution 1. Recursion(재귀) - DFS

public TreeNode invertTree(TreeNode root) {

    //1. Recursion - DFS
    if(root == null) return root;

    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);

    return root;
}

재귀호출을 이용한 깊이우선탐색(DFS) 을 통하여 left,right 노드를 swap 해줍니다.

Solution 2. Iteration(반복) - BFS

public TreeNode invertTree2(TreeNode root) {

    //2. Iteration - BFS
    if(root == null) return root;

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while(!q.isEmpty()){
        TreeNode cur = q.poll();
        TreeNode temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;
        if(cur.left !=null) q.offer(cur.left);
        if(cur.right !=null) q.offer(cur.right);
    }

    return root;
}

큐를 이용하여 반복적으로 너비우선탐색(BFS)를 통하여 left,right값을 swap해 나가는 방법입니다.

Reference

Invert Binary Tree - LeetCode