99클럽 코테 스터디 11일차 TIL + 이진트리, DFS, BFS

✨ 문제 

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

 

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/

 

 

 

✨ 개념

이진 트리

- 분할 정복 탐색 알고리즘으로 빠른 속도로 탐색 가능

- 모든 노드가 2개의 서브 트리를 갖는 트리. 서브트리는 공집합일 수 있음.

- 모든 노드가 최대 2개의 자식 노드가 존재할 수 있음.

- 모든 노드의 차수가 2 이하.

- 이진 트리에는 서브 트리간 순서가 존재하며 왼쪽 트리와 오른쪽 트리가 구별됨.

 

이진 트리 성질

- n개의 노드를 가진 이진트리의 간선 개수 : n-1

- 높이가 h인 이진트리는 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가짐.

- 레벨 i에서의 최대 노드개수 : 2^(i-1)개

 

 

DFS (Depth First Search)

- 스택 또는 재귀를 사용해 구현 가능

- 한 정점에서 최대한 깊게 탐색 후 더이상 방문 가능한 정점이 없으면 이전 정점으로 돌아와 다시 탐색하는 과정을 반복함.

 

BFS (Breadth First Search)

- 두 노드 사이의 최단 경로 또는 임의의 경로를 찾을 때 사용.

- 시작 노드에서 가까운 노드를 우선 탐색하며, 그래프나 트리 탐색에 사용됨.

- 보통 큐를 사용해 구현.

 

 

 

✨ 최종코드

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

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (!original)
            return nullptr;
        if (original == target)
            return cloned;
        
        TreeNode* leftResult = getTargetCopy(original->left, cloned->left, target);
        if (leftResult)
            return leftResult;
        
        return getTargetCopy(original->right, cloned->right, target);
    }
};