##### Welcome to Subscribe On Youtube
• /*
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.

*/

public class Subtree_of_Another_Tree {

public static void main(String[] args) {
Subtree_of_Another_Tree out = new Subtree_of_Another_Tree();
Solution s = out.new Solution();

TreeNode root = new TreeNode(3);
root.left = new TreeNode(4);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(2);

TreeNode t = new TreeNode(4);
t.left = new TreeNode(1);
t.right = new TreeNode(2);

System.out.println(s.isSubtree(root, t));
}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {

if(s == null && t == null) {
return true;
}

if((s == null && t != null) || (s != null && t == null)) {
return false;
}

// key is to have a same tree check, or else will be skip level same
return isSameTree(s, t) || isSubtree(s.left, t) || (isSubtree(s.right, t));
}

public boolean isSameTree(TreeNode s, TreeNode t) {

if(s == null && t == null) {
return true;
}

if((s == null && t != null) || (s != null && t == null)) {
return false;
}

return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
}
}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
return dfs(root, subRoot) || isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}

private boolean dfs(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
return root1.val == root2.val && dfs(root1.left, root2.left)
&& dfs(root1.right, root2.right);
}
}

• // OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
// Time: O(ST) where S and T are the node count of s and t.
// Space: O(H) where H is the height of s.
class Solution {
private:
bool isSameTree(TreeNode* s, TreeNode* t) {
return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
}
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
def dfs(root1, root2):
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
return (
root1.val == root2.val
and dfs(root1.left, root2.left)
and dfs(root1.right, root2.right)
)

if root is None:
return False
return (
dfs(root, subRoot)
or self.isSubtree(root.left, subRoot)
or self.isSubtree(root.right, subRoot)
)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""

def serialize(root):
ans = []
stack = [(root, 1)]
while stack:
node, p = stack.pop()
if not node:
ans.append("#")
continue
if p == 0:
ans.append("|" + str(node.val))
else:
stack.append((node.right, 1))
stack.append((node.left, 1))
stack.append((node, 0))
return ",".join(ans)

return serialize(t) in serialize(s)


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
if root == nil {
return false
}
var dfs func(root1, root2 *TreeNode) bool
dfs = func(root1, root2 *TreeNode) bool {
if root1 == nil && root2 == nil {
return true
}
if root1 == nil || root2 == nil {
return false
}
return root1.Val == root2.Val && dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)
}
return dfs(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

const dfs = (root: TreeNode | null, subRoot: TreeNode | null) => {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null || root.val !== subRoot.val) {
return false;
}
return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
};

function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
if (root == null) {
return false;
}
return (
dfs(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot)
);
}


• /**
* 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} root
* @param {TreeNode} subRoot
* @return {boolean}
*/
var isSubtree = function (root, subRoot) {
if (!root) return false;
let dfs = function (root1, root2) {
if (!root1 && !root2) {
return true;
}
if (!root1 || !root2) {
return false;
}
return (
root1.val == root2.val &&
dfs(root1.left, root2.left) &&
dfs(root1.right, root2.right)
);
};
return (
dfs(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot)
);
};


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, sub_root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
if root.is_none() && sub_root.is_none() {
return true;
}
if root.is_none() || sub_root.is_none() {
return false;
}
let root = root.as_ref().unwrap().borrow();
let sub_root = sub_root.as_ref().unwrap().borrow();
root.val == sub_root.val
&& Self::dfs(&root.left, &sub_root.left)
&& Self::dfs(&root.right, &sub_root.right)
}

fn help(
root: &Option<Rc<RefCell<TreeNode>>>,
sub_root: &Option<Rc<RefCell<TreeNode>>>,
) -> bool {
if root.is_none() {
return false;
}
Self::dfs(root, sub_root)
|| Self::help(&root.as_ref().unwrap().borrow().left, sub_root)
|| Self::help(&root.as_ref().unwrap().borrow().right, sub_root)
}

pub fn is_subtree(
root: Option<Rc<RefCell<TreeNode>>>,
sub_root: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
Self::help(&root, &sub_root)
}
}


• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null)
return t == null;
if (t == null || same(s, t))
return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

public boolean same(TreeNode s, TreeNode t) {
if (s == null && t == null)
return true;
if (s == null || t == null)
return false;
return s.val == t.val && same(s.left, t.left) && same(s.right, t.right);
}
}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
return dfs(root, subRoot) || isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}

private boolean dfs(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
return root1.val == root2.val && dfs(root1.left, root2.left)
&& dfs(root1.right, root2.right);
}
}

• // OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
// Time: O(ST) where S and T are the node count of s and t.
// Space: O(H) where H is the height of s.
class Solution {
private:
bool isSameTree(TreeNode* s, TreeNode* t) {
return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
}
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
def dfs(root1, root2):
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
return (
root1.val == root2.val
and dfs(root1.left, root2.left)
and dfs(root1.right, root2.right)
)

if root is None:
return False
return (
dfs(root, subRoot)
or self.isSubtree(root.left, subRoot)
or self.isSubtree(root.right, subRoot)
)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""

def serialize(root):
ans = []
stack = [(root, 1)]
while stack:
node, p = stack.pop()
if not node:
ans.append("#")
continue
if p == 0:
ans.append("|" + str(node.val))
else:
stack.append((node.right, 1))
stack.append((node.left, 1))
stack.append((node, 0))
return ",".join(ans)

return serialize(t) in serialize(s)


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
if root == nil {
return false
}
var dfs func(root1, root2 *TreeNode) bool
dfs = func(root1, root2 *TreeNode) bool {
if root1 == nil && root2 == nil {
return true
}
if root1 == nil || root2 == nil {
return false
}
return root1.Val == root2.Val && dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)
}
return dfs(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

const dfs = (root: TreeNode | null, subRoot: TreeNode | null) => {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null || root.val !== subRoot.val) {
return false;
}
return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
};

function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
if (root == null) {
return false;
}
return (
dfs(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot)
);
}


• /**
* 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} root
* @param {TreeNode} subRoot
* @return {boolean}
*/
var isSubtree = function (root, subRoot) {
if (!root) return false;
let dfs = function (root1, root2) {
if (!root1 && !root2) {
return true;
}
if (!root1 || !root2) {
return false;
}
return (
root1.val == root2.val &&
dfs(root1.left, root2.left) &&
dfs(root1.right, root2.right)
);
};
return (
dfs(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot)
);
};


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, sub_root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
if root.is_none() && sub_root.is_none() {
return true;
}
if root.is_none() || sub_root.is_none() {
return false;
}
let root = root.as_ref().unwrap().borrow();
let sub_root = sub_root.as_ref().unwrap().borrow();
root.val == sub_root.val
&& Self::dfs(&root.left, &sub_root.left)
&& Self::dfs(&root.right, &sub_root.right)
}

fn help(
root: &Option<Rc<RefCell<TreeNode>>>,
sub_root: &Option<Rc<RefCell<TreeNode>>>,
) -> bool {
if root.is_none() {
return false;
}
Self::dfs(root, sub_root)
|| Self::help(&root.as_ref().unwrap().borrow().left, sub_root)
|| Self::help(&root.as_ref().unwrap().borrow().right, sub_root)
}

pub fn is_subtree(
root: Option<Rc<RefCell<TreeNode>>>,
sub_root: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
Self::help(&root, &sub_root)
}
}