[LeetCode | Java | Tree 문제 풀이] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

99클럽 | Begginer

🐾 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

🏷 Topic : Tree Binary Tree BFS DFS

Easy

---

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.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown.

The target node is a green node from the original tree.

The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target = 7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• The values of the nodes of the tree are unique.
• target node is a node from the original tree and is not null.

Accepted 228.1K | Submissions 265.8K | Acceptance Rate 85.8%

---

✔ Solution with DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    TreeNode t;
    TreeNode ans;

    public void searchNode(TreeNode node, TreeNode cNode) {
        if (node != null) {
            searchNode(node.left, cNode.left);
            if (node == t) {
                ans = cNode;
            }
            searchNode(node.right, cNode.right);
        }

    }
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        t = target;

        searchNode(original, cloned);

        return ans;
    }
}

채점 결과

💥 어떤 문제가 있었고, 어떤 시도를 했는지💦 & 어떻게 해결했는지👍

재귀함수로 DFS(Depth First Search)를 구현하려고 했는데 잘 안되어서 Editorial을 보고 답을 썼다.

영어로 써 있어서 답인지 DFS, BFS 등 관련 개념 설명인지 잘 모른 채로 따라 쓰고 제출을 했는데 답안지였나보다😜

내가 푼 풀이 외에 다른 풀이도 있었는데 조금 더 공부를 해 봐야겠다.

💬 무엇을 새롭게 알았는지

DFS로 노드 탐색하는 코드 구현하기

---

📚 References(참고 자료)

LeetCode | 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree | Editorial

[Java 봐 | 자료 구조] 트리(Tree) 개념 정리