[Leetcode]1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

문제 요약

• 알고리즘 분류: Tree, DFS, BFS
• 난이도: Easy
• 문제내용:
  • cloned Tree에서  taget Node 것을 반환 하여라 
• 사이트 주소: https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/

문제풀이

 이번 문제는 이진트리와 트리에 대한 탐색을 활용한 간단한 문제이다. 이번 문제는 트리 탐색중 깊이 우선 탐색으로 설명 할것이다.

트라와 깊이 우선 탐색(DFS)에 대한 자세한 설명은 아래 글에서 확인 해보면 된다.

• 트리: https://jih3508.tistory.com/87
• 깊이 우선 탐색(DFS): https://jih3508.tistory.com/94
• 넓이 우선 탐색(BFS): https://jih3508.tistory.com/96

아래와 같이 구현 하면된다.(DFS할때는 stack을 사용하고 BFS 할때는 queue를 사용한다.)

1. stack이나 queue에서 cloned 트리 루트를 담아서 선언한다.
2. stack이나 queue에서 값이 비어 질때 까지 아래를 탐색 한다.
3. stack이나 queue에서 값을 꺼내고 그 값이 target value와 같으면 반환하고 없으면 stack이나 queue에서 자식 노드를 담는다.

위와 같이 구현 했을때는 시간 복잡도는 노드 개수 N개일때  전체 노드 탐색 하기 때문에 O(N) 나온다.

Code

DFS

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

        stack = [cloned]

        while stack:
            now = stack.pop()

            # 같은 노드 이면 반환
            if now.val == target.val:
                return now

            # 왼쪽 노드 있으면 stack에 추가
            if now.left:
                stack.append(now.left)

            # 오른쪽 노드 있으면 stack에 추가
            if now.right:
                stack.append(now.right)

Java

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(cloned);

        while(!stack.isEmpty()){
            TreeNode now = stack.pop();

            // 같은 노드 이면 반환
            if(now.val == target.val){
                return now;
            }

            // 왼쪽 노드 있으면 stack에 추가
            if(now.left != null){
                stack.push(now.left);
            }

            // 왼쪽 노드 있으면 stack에 추가
            if(now.right != null){
                stack.push(now.right);
            }

        }
        
        return null;
    }

Javascript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var getTargetCopy = function(original, cloned, target) {

    let stack = Array();
    stack.push(cloned);

    while(stack){
        const node = stack.pop();
        // 같은 노드 이면 반환
        if(node.val === target.val){
            return node;
        }

        // 왼쪽 노드 있으면 stack에 추가
        if(node.left){
            stack.push(node.left);
        }

        // 왼쪽 노드 있으면 stack에 추가
        if(node.right){
            stack.push(node.right);
        }

    }

};

BFS

Python

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

        queue =  deque([cloned])

        while queue:
            now = queue.popleft()

            # 같은 노드 이면 반환
            if now.val == target.val:
                return now

            # 왼쪽 노드 있으면 stack에 추가
            if now.left:
                queue.append(now.left)

            # 오른쪽 노드 있으면 stack에 추가
            if now.right:
                queue.append(now.right)

Java

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(cloned);

        while(!queue.isEmpty()){
        TreeNode now = queue.poll();

            // 같은 노드 이면 반환
            if(now.val == target.val){
              return now;
            }

            // 왼쪽 노드 있으면 stack에 추가
            if(now.left != null){
                queue.add(now.left);
            }

            // 왼쪽 노드 있으면 stack에 추가
            if(now.right != null){
                queue.add(now.right);
            }

        }

        return null;
    }
}

Javascript

var getTargetCopy = function(original, cloned, target) {

    class Queue{
        constructor(){
            this.items = [];
            this.start = 0;
            this.end = 0;
            this.size = 0;
        }


        push(val){
            this.items.push(val);
            this.size++;
            this.end += 1;
        }

        pop(){
            this.size--;
            return this.items[this.start++]
        }

        isEmpty(){
            return this.size === 0;
        }
    }

    let queue = new Queue();
    queue.push(cloned);

    while(!queue.isEmpty()){
        const node = queue.pop();
        // 같은 노드 이면 반환
        if(node.val === target.val){
            return node;
        }

        // 왼쪽 노드 있으면 stack에 추가
        if(node.left){
            queue.push(node.left);
        }

        // 왼쪽 노드 있으면 stack에 추가
        if(node.right){
            queue.push(node.right);
        }

    }

};