Knock algorithm series articles

- Ten classic sorting algorithms for dry goods and hand tearing
- Sword finger offer | understanding interview
- Sword finger offer | interview question 2: realizing Singleton mode
- Sword finger offer | interview question 3: finding two-dimensional array
- Sword finger offer | interview question 4: replace spaces
- Sword finger offer | interview question 5: print linked list from end to end
- Jianzhi offer | interview question 6: Rebuilding binary tree
- Sword finger offer | interview question 7: realizing queue with two stacks
- Sword finger offer | interview question 8: minimum number of rotation array
- Sword finger offer | interview question 9: Fibonacci sequence
- Sword finger offer | interview question 10: frog jumping steps
- Sword finger offer | interview question 11: matrix coverage
- Sword finger offer | interview question 12: the number of 1 in binary
- Sword finger offer | interview question 13: integer power of value
- Sword finger offer | interview question 14: print from 1 to the maximum n digits
- Sword finger offer | interview question 15: delete the node of the linked list
- Sword finger offer | interview question 16: put the odd number in the array before the even number
- Sword finger offer | interview question 17: the penultimate node in the lin k ed list
- Sword finger offer | interview question 18: reverse linked list
- Sword finger offer | interview question 19: merge two ordered linked lists

"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:

- First traverse each node nA in tree A; (corresponding function isSubStructure(A, B))
- 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:

- Termination conditions:
- When node B is empty: it indicates that tree B has been matched (crossing the leaf node), so it returns true;
- 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;
- When the values of nodes A and B are different: it indicates that the matching fails and returns false;

- Return value:
- Judge whether the left child nodes of a and B are equal, that is, recur(A. left, B. left);
- Judge whether the right child nodes of a and B are equal, that is, recur(A. right, B. right);

isSubStructure(A, B) function:

- Special case handling: when tree A is empty or tree B is empty, false is returned directly;
- 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;
- The subtree with node A as the root node contains tree B, corresponding to recur(A,B);
- Tree B is the substructure of the left subtree of tree a, corresponding to isSubStructure(A. left, B);
- 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 { /** * Selected answers * @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; } } }

Reference link: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p

The revolution has not yet succeeded, and comrades still need to work hard and rush