572. Subtree of Another Tree
Description
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example 1: Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2: Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
* @param {TreeNode} s
* @param {TreeNode} t
* @return {boolean}
*/
var isSubtree = function(s, t) {
"use strict";
function match(node1, node2) {
if (node1 && node2) {
if (node1.val === node2.val) {
return match(node1.left, node2.left) &&
match(node1.right, node2.right);
} else {
return false;
}
} else {
return node1 === node2;
}
}
function dfs(node) {
if (node) {
if (node.val === t.val) {
if (match(node, t)) {
return true;
}
}
return dfs(node.left) || dfs(node.right);
}
}
return dfs(s) || false;
};