Sword finger offer | interview question 20: judge whether binary tree A contains subtree B

Knock algorithm series articles

"Leetcode : https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

"GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_20_isSubStructure/Solution.java

Judge whether binary tree A contains subtree B

Title Description: 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.

Example 1:

```Input: A = [1,2,3], B = [3,1]
Output: false
```

Example 2:

```Input: A = [3,4,5,1,2], B = [4,1]
Output: true
```

Limit: 0 < = number of nodes < = 10000

Solution: if tree B is A substructure of tree A, the root node of the substructure may be any node of tree A. Therefore, to judge whether tree B is A substructure of tree A, the following two steps need to be completed:

1. First traverse each node nA in tree A; (corresponding function isSubStructure(A, B))
2. Judge whether the subtree with nA as the root node in tree A contains tree B. (corresponding function recur(A,B))
Algorithm flow:

"The noun stipulates that the root node of tree A is recorded as node A, and the root node of tree B is called node B.

recur(A, B) function:

1. Termination conditions:
1. When node B is empty: it indicates that tree B has been matched (crossing the leaf node), so it returns true;
2. When node A is empty: it indicates that it has crossed the leaf node of tree A, that is, matching fails and false is returned;
3. When the values of nodes A and B are different: it indicates that the matching fails and returns false;
2. Return value:
1. Judge whether the left child nodes of a and B are equal, that is, recur(A. left, B. left);
2. Judge whether the right child nodes of a and B are equal, that is, recur(A. right, B. right);

isSubStructure(A, B) function:

1. Special case handling: when tree A is empty or tree B is empty, false is returned directly;
2. Return value: if tree B is A substructure of tree A, it must meet one of the following three conditions, so use or to connect;
1. The subtree with node A as the root node contains tree B, corresponding to recur(A,B);
2. Tree B is the substructure of the left subtree of tree a, corresponding to isSubStructure(A. left, B);
3. Tree B is the substructure of the right subtree of tree a, corresponding to isSubStructure(A. right, B);

To make 2 3. It is essentially A preorder traversal of tree A.

Complexity analysis:

• Time complexity O(MN): m and N are the number of nodes of tree A and tree B respectively; The tree a is traversed in sequence, occupying 0(M), and each time recur(A, B) is called to judge the occupation of O(N).
• Space complexity O:
• When both tree A and tree B degenerate into linked lists, the recursive call depth is the largest.
• When M ≤ N, the total recursive depth of traversing tree A and recursive judgment is M;
• When M > N, the worst case is to traverse to the leaf node of tree A, and the total recursion depth is M.
```package com.nateshao.sword_offer.topic_20_isSubStructure;

/**
* @date Created by Shao Tongjie on 2021/11/23 19:19
* @WeChat official account programmers
* @Personal website www.nateshao.com cn
* @Blog https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: Judge whether binary tree A contains subtree B
*/
class Solution {

/**
* @param A
* @param B
* @return
*/
public static boolean isSubStructure1(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur1(A, B) || isSubStructure1(A.left, B) || isSubStructure1(A.right, B));
}

public static boolean recur1(TreeNode A, TreeNode B) {
if (B == null) return true;
if (A == null || A.val != B.val) return false;
return recur1(A.left, B.left) && recur1(A.right, B.right);
}

/*********************************** Method II*********************************************/
//Traverse each node of A
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) return false;//The contract empty tree is not a substructure of any tree
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

//Traverse the same location nodes of A and B at the same time
boolean recur(TreeNode A, TreeNode B) {
//When a node of B is null, there is no need to compare. It directly returns true to compare other nodes
if (B == null) return true;
//If two nodes in the same location are different, false will be returned. There is no need to continue the comparison
if (A == null || A.val != B.val) return false;
//Continue to traverse the comparison
return recur(A.left, B.left) && recur(A.right, B.right);
}

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

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