leetcode/sameTree.ts at master · thinhphamdn1999/leetcode · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import { TreeNode } from './types/tree';

function originalBFS(root: TreeNode | null) {
	const queue = [];
	queue.unshift(root);
	let node;
	while (queue.length !== 0) {
		node = queue.pop();
		if (!!node.left) {
			queue.unshift(node.left);
		}

		if (!!node.right) {
			queue.unshift(node.right);
		}
	}
}

function findSameTreeBFS(firstTree: TreeNode | null, secondTree: TreeNode | null) {
	const firstTreeQueue = [];
	const secondTreeQueue = [];
	firstTreeQueue.unshift(firstTree);
	secondTreeQueue.unshift(secondTree);
	let firstTreeNode: TreeNode;
	let secondTreeNode: TreeNode;
	let sameTree;

	while (firstTreeQueue.length !== 0 && secondTreeQueue.length !== 0) {
		firstTreeNode = firstTreeQueue.pop();
		secondTreeNode = secondTreeQueue.pop();

		sameTree =
			firstTreeNode?.val === secondTreeNode?.val &&
			firstTreeNode?.left?.val === secondTreeNode?.left?.val &&
			firstTreeNode?.right?.val === secondTreeNode?.right?.val;

		if (!sameTree) {
			return false;
		}

		if (!!firstTreeNode?.left) {
			firstTreeQueue.unshift(firstTreeNode.left);
		}

		if (!!firstTreeNode?.right) {
			firstTreeQueue.unshift(firstTreeNode.right);
		}

		if (!!secondTreeNode?.left) {
			secondTreeQueue.unshift(secondTreeNode.left);
		}

		if (!!secondTreeNode?.right) {
			secondTreeQueue.unshift(secondTreeNode.right);
		}
	}

	if (firstTreeQueue.length > 0 || secondTreeQueue.length > 0) {
		return false;
	}

	return true;
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
	return findSameTreeBFS(p, q);
}

const p = new TreeNode(1);
p.left = new TreeNode(null);
p.right = new TreeNode(2);
p.right.left = new TreeNode(3);

const q = new TreeNode(1);
q.left = new TreeNode(null);
q.right = new TreeNode(2);
q.right.left = new TreeNode(null);
q.right.right = new TreeNode(3);

console.log(isSameTree(p, q));