-
[LeetCode] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree c++Coding Test/LeetCode 2022. 9. 26. 15:17728x90
- 문제
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.
original 트리에 target노드를 찾는 문제이다.
- 문제 해결
TreeNode* ans; TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) { if(cloned == NULL) return cloned; if(cloned->val == target->val){ ans = cloned; } getTargetCopy(original, cloned->left, target); getTargetCopy(original, cloned->right, target); return ans; }
다른 방법1
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) { if (!original) return NULL; if (original == target) return cloned; TreeNode* Lt = getTargetCopy(original->left, cloned->left, target); if (Lt) return Lt; return getTargetCopy(original->right, cloned->right, target); }
다른 방법2
TreeNode* getTargetCopy3(TreeNode* original, TreeNode* cloned, TreeNode* target) { std::queue<TreeNode*> que; que.push(cloned); while (!que.empty()) { int n = que.size(); TreeNode* curnode = que.front(); que.pop(); if (curnode->val == target->val) { return curnode; } if (curnode->left) { que.push(curnode->left); } if (curnode->right) que.push(curnode->right); } return cloned; }
728x90'Coding Test > LeetCode' 카테고리의 다른 글
[LeetCode] 2331. Evaluate Boolean Binary Tree c++ (0) 2022.09.26 [LeetCode] 938. Range Sum of BST c++ (0) 2022.09.26 [LeetCode] 27. Remove Element c++ (0) 2022.09.15 [LeetCode] 26. Remove Duplicates from Sorted Array c++ (0) 2022.09.15 [LeetCode] 1. Two Sum c++ (0) 2022.09.14