(C++) - LeetCode (easy) 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

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

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

tree 순회 dfs 문제였습니다.

📕 풀이방법

📔 풀이과정

getTargetCopy를 dfs로 순회하며 origin과 target이 같은 경우의 TreeNode를 copy에서 찾아 반환합니다. 재귀 logic은 다음과 같습니다.

1. origin과 copy는 같으므로 origin 이 NULL이면 target과 같은 treeNode가 없는 것이므로 NULL을 반환합니다.

2. 현재 확인한 origin이 target과 같다면 정답을 찾았으므로 copy를 반환합니다.

3. 왼쪽 subtree와 오른쪽 subtree의 결과값을 지역변수 left와 right에 각각 저장합니다.

📔 정답 출력 | 반환

left와 right중 NULL이 아닌 것이 정답이므로 해당하는 변수를 반환합니다. 

---

📕 Code

📔 C++

/**
 * 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 == NULL) return NULL;
        if(original == target) return cloned;
        TreeNode *left = getTargetCopy(original->left, cloned->left, target);
        TreeNode *right = getTargetCopy(original->right, cloned->right, target);
        return  left != NULL ? left : right;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.