[알고리즘]_[LeetCode]- 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

SAPCO·2022년 7월 19일

- [Algorithm]

목록 보기

7/13

📍 1. 문제

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

📍 2. 풀이

📌 2-1. 풀이 (dfs reculsive)

(1) 방법

원본트리에서의 target Node에 상응하는 클론트리의 Node를 찾는 문제.
inorder preorder postorder등 정처기에서 한번 쯤 봤었을 전위, 후위, 중위순회 중 inorder(중위순회 left-root-right)로 풀이.

(2) 코드

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

class Solution {
    TreeNode target , res;
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        this.target = target;
        inorder(original, cloned);
        return res;
    }
    
    public void inorder(TreeNode origin , TreeNode clone) {
        if(origin != null) {
            inorder(origin.left, clone.left);
            if(origin == target) {
                res = clone;
            }
            inorder(origin.right, clone.right);
        }
        
    }
}