Leetcode 100 - Same tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example:

img

1
2
Input: p = [1,2,3], q = [1,2,3]
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;

return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

A naive way using BFS

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
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
let traversal_p = [];
let traversal_q = [];
bfs(p, traversal_p);
bfs(q, traversal_q);
return traversal_p.toString() == traversal_q.toString();

function bfs(node, arr) {
if (!node) {
arr.push(null);
return;
}
if (node) {
arr.push(node.val);
}
bfs(node.left, arr);
bfs(node.right, arr);
}
};