최근에 저는 알고리즘/데이터 구조 기술을 향상시키기 위해 LeetCode 연습을 몇 가지 연습하기 시작했습니다. 이 플랫폼은 여러 프로그래밍 언어로 다른 개발자 솔루션을 연습하고 배우고, 토론하고, 다른 사람들과 솔루션을 공유하고, 대기업에서 요청한 코드 과제를 연습할 수 있는 좋은 환경을 제공한다고 말할 수 있습니다.

LeetCode란 무엇인가요?

LeetCode는 후보자가 코딩 인터뷰를 준비하는 데 도움을 주는 웹사이트입니다. 사용자는 후보자의 솔루션에 대해 사전 정의된 테스트와 함께 플랫폼의 코딩 및 알고리즘 문제를 사용하여 과제를 연습할 수 있습니다. LeetCode는 HackerRank와 함께 기술 인터뷰 및 코딩 대회를 위한 인기 있는 리소스가 되었습니다.

나의 일상적인 문제 해결

저는 하루에 최소 3개의 과제를 해결한다는 목표를 세웠으며, 솔루션에 대한 저의 사고 방식은 iPad, 화면용 펜, Freeform 앱을 포함합니다. 나는 해결책에 대해 그림을 그리고 생각하려고 노력하는데, 이는 코드 제출에 많은 도움이 됩니다. 언뜻 보면 많은 과제가 어려워 보이지만 몇 분만 투자하면 솔루션을 생각하고 설계할 수 있습니다(사고 과정을 작성하는 것이 좋습니다). 30분 내에 올바른 솔루션을 찾을 수 없으면 다른 개발자의 제출물을 보고 내 실수가 어디에 있는지 알아냅니다(때로는 코드에서 잊어버린 작은 단계임). 귀하의 솔루션이 충분히 훌륭하더라도 다른 사람의 제출물을 살펴보고 해당 문제를 해결하는 다른 방법(다소 효율적인 방법도 있음)을 생각해 보는 것이 좋습니다.

역 이진 트리 문제

며칠 전 저는 LeetCode에서 Invert Binary Tree 문제에 직면했습니다. 이는 일부 인터뷰에서 요청한 잘 알려진 문제이자 대학에서 데이터 구조/알고리즘 수업을 들을 때 본 문제입니다. 인터뷰에서 이러한 문제에 직면한 적이 없고 작업에서 이진 트리를 명시적으로 반전해 본 적이 없지만 반전하는 방법을 아는 것은 나에게 DS, 트리 및 알고리즘 사고에 대한 더 많은 경험을 제공하고 재귀와 같은 일부 기술을 연습할 수 있게 해주었습니다.
이 문서의 나머지 부분을 읽기 전에 이 문제를 해결해 보시기 바랍니다.

해결책

역 이진 트리 문제는 "이진 트리의 루트가 주어지면 트리를 반전하고 그 루트를 반환"하도록 요청했습니다. (즉, 트리를 "미러링"해야 합니다). 솔루션을 제출하기 위해 Java 프로그래밍 언어를 사용했지만 단계는 다른 언어에서도 동일합니다(구문이 약간 변경됨). 입력 예와 예상 출력은 다음과 같습니다.

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

재귀 기술을 사용하여 invertTree() 메서드를 재귀적으로 호출하고 트리의 일부 측면을 루트로 전달하겠습니다. 따라서 모든 재귀가 요구하는 대로 재귀 스택이 종료되고 재귀 호출의 해당 결과를 반환하는 중지 조건을 정의해야 합니다. 그런 다음, 트리의 측면을 뒤집어서 root.right를 매개변수로 전달하는 재귀에서 반환된 값을 root.left에 할당하고, root.left 재귀 결과의 값을 할당하여 root.right에도 동일한 작업을 수행합니다. 원래 값을 수정하므로 root.left의 원래 결과를 저장할 보조 변수가 필요합니다 (아마 대학에서 이와 같은 코드를 구현하고 이를 swap() 메서드라고 불렀을 것입니다.

마지막에는 노드가 반전된 루트를 반환합니다. 아래 코드를 확인할 수 있습니다:

/**
 * 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 invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

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

        return root;
    }
}

다양한 문제에 대해 다양한 솔루션이 존재할 수 있다는 점을 명심하세요. 정말 좋습니다. 모든 사람은 데이터 구조 도메인 등의 사고 방식과 프로그래밍 방식을 가지고 있습니다. 이 문제를 해결하기 위해 정확히 동일한 코드를 따를 필요는 없지만 알고리즘 복잡성에 주의해야 합니다(문제를 해결하려면 3개의 중첩된 for를 사용할 수 있음). , 그러나 이는 1을 사용하는 것보다 성능이 떨어집니다.