[algo / Neetcode] invert binary tree

문제 링크

C++ 정리 - struct 관련

문제에 나온 TreeNode struct 분석

struct TreeNode {
    int val;           // 이 노드가 저장할 값 (예: 숫자 1, 2, 3...)
    TreeNode *left;    // 왼쪽 자식 노드의 주소를 가리키는 포인터
    TreeNode *right;   // 오른쪽 자식 노드의 주소를 가리키는 포인터

    // 아래 3줄은 노드를 쉽게 만들기 위한 "생성자(Constructor)"입니다.
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode node; 혹은 TreeNode* ptr 라고 했을 때

구조체 내부 접근

• 일반 구조체 변수 . 사용 : node.val = 10;
• 구조체 포인터 -> 사용 : ptr->val = 10;

일반 구조체 변수와 구조체 포인터의 차이점

• 저장하는 내용의 차이
  일반 구조체 변수: 데이터 값 자체를 메모리에 직접 저장함
  구조체 포인터: 구조체 데이터가 실제로 존재하는 메모리의 주소값만 저장함
• 메모리 크기의 차이
  일반 구조체 변수: 내부 멤버 변수들의 크기 합만큼 메모리를 크게 차지함
  구조체 포인터: 내부 멤버가 얼마나 크든 상관없이 항상 고정된 주소값 크기만 차지함 (32비트 4바이트, 64비트 8바이트)
• 멤버 접근 기호의 차이
  일반 구조체 변수: 마침표(.) 기호를 사용함 (node.val)
  구조체 포인터: 화살표(->) 기호를 사용함 (node_ptr->val)
• 함수 인자 전달 시 동작 차이
  일반 구조체 변수: 함수에 전달할 때 데이터 전체가 복사되어 전달됨 (수정해도 원본에 영향 없음)
  구조체 포인터: 주소만 전달되므로 함수 내부에서 원본 데이터를 직접 수정할 수 있음
• 빈 값(비어있음) 표현 가능 여부
  일반 구조체 변수: 항상 실체가 존재해야 해서 null 상태를 표현하기 어려움
  구조체 포인터: 가리키는 대상이 없을 때 nullptr로 비어있는 상태를 명확히 표현할 수 있음

---

풀이

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {

    }
};

모든 노드의 왼쪽 오른쪽 자식 위치 바꾸는 문제

• 트리 문제는 재귀 방식으로 접근하면 됨 (root -> leaf 노드로)

• 현재 root 의 왼쪽과 오른쪽을 swap

• 이후 root 의 왼쪽과 오른쪽에 대해 swap 하는 것을 재귀적으로 수행

• 재귀 후 root 노드 반환

• 참고 : 일반 구조체 변수 node로 주면 아래 연결된 노드들 전체를 복사해서 전달해야 됨. 따라서 문제에서는 맨 위 시작 노드인 root 의 포인터 주소로 struct 제공함

메모리 상에서 일어나는 일

• root->val: 루트 노드의 값인 1에 접근함
• root->left: 왼쪽 자식 노드(val: 2)가 있는 주소
• root->right: 오른쪽 자식 노드(val: 3)가 있는 주소

---

최종 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        std::swap(root->left, root->right);

        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

• 문제 자체가 어렵다기 보다는 struct 이 기억안나서 헤맨 게 더 큰 것 같다