# 剑指 Offer 26. 树的子结构(Sword finger offer 26 Substructure of tree)-其他

## 剑指 Offer 26. 树的子结构(Sword finger offer 26 Substructure of tree)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

``````
3
/ \
4   5
/ \
1   2
``````

``````
4
/
1
``````

### 递归

``````class Solution {
public boolean isSubStructure(TreeNode root1, TreeNode root2) {
return (root1 != null && root2 != null) && (isSame(root1, root2) || isSubStructure(root1.left, root2) || isSubStructure(root1.right, root2));
}

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

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

``````
————————

Input two binary trees a and B to judge whether B is the substructure of A. (the contract empty tree is not a substructure of any tree)

B is the substructure of a, that is, the same structure and node values as B appear in a.

For example:
Given tree A:

``````
3
/ \
4   5
/ \
1   2
``````

Given tree B:

``````
4
/
1
``````

Returns true because a subtree of B and a has the same structure and node values.

Source: leetcode

### recursion

``````class Solution {
public boolean isSubStructure(TreeNode root1, TreeNode root2) {
return (root1 != null && root2 != null) && (isSame(root1, root2) || isSubStructure(root1.left, root2) || isSubStructure(root1.right, root2));
}

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

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

``````