-
Notifications
You must be signed in to change notification settings - Fork 6
/
getTargetCopy.test.js
40 lines (29 loc) · 1.14 KB
/
getTargetCopy.test.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/
// TEST: npm test ./leetcode/medium/getTargetCopy.test.js
// 0(n) - time | 0(1) - space
const BST = require("../easy/BST-testcase.test");
describe('#Get target copy from a cloned BT', () => {
let p, q;
beforeEach(() => {
p = new BST()
p.insert(p.root, 60); p.insert(p.root, 10)
p.insert(p.root, 40); p.insert(p.root, 70)
p.insert(p.root, 20); p.insert(p.root, 5)
q = p.copy()
})
it('returns the target in the cloned tree', () => {
expect(getTargetCopy(p.root, q, 20).data).toBe(20)
expect(getTargetCopy(p.root, q, 60).data).toBe(60)
})
})
const getTargetCopy = (original, cloned, target) => {
if (!original || !cloned) return
const dfs = (original, copy) => {
if (!original) return
if (original.data === target) return copy // in leetcode playground, compare the original node, not just the target. This will cover the edge case of duplicate values
let left = dfs(original.left, copy.left)
let right = dfs(original.right, copy.right)
return left || right
}
return dfs(original, cloned)
}