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:

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

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;
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 {

    /**
     * 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

Added by swizenfeld on Wed, 29 Dec 2021 13:40:33 +0200

Programming VIP

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

Judge whether binary tree A contains subtree B

Algorithm flow:

Popular Keywords