Title Description

Input two binary trees a and B to determine whether B is a substructure of A. (ps: we agree that an empty tree is not a substructure of any tree)

Key words: binary tree

thinking

subtree
A big tree a, a small tree B. if B is a subtree of a, then:

• The node values of B and A are exactly the same, and the values of all nodes of their left and right subtrees are also exactly the same
• Or B's left child and A's node values are exactly the same, so are all the nodes of their left and right subtrees
• Or B's right child and A's node values are exactly the same, so are the left and right subtrees

Substructure
The substructure is not so strict. The small box in the figure is the substructure of the whole tree, and the large yellow box in the figure is also the substructure of the whole tree, so as long as a part of the tree node is found

Therefore, you can write functions to determine whether root2 is a subtree / substructure of root1. The difference is that the subtree is a direct branch of the node, and the root node must be the left or right node of the parent object. And the substructure can be an indirect branch structure

code implementation

subtree

Links: https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88?answerType=1&f=discussion
//Source: niuke.com

public class IsSubTree {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return judgeSubTree(root1, root2) ||
               judgeSubTree(root1.left, root2) ||
               judgeSubTree(root1.right, root2);
    }
 	
 	//The (sequential) function is used to determine whether two root s are equal
    private boolean judgeSubTree(TreeNode root1, TreeNode root2) {
    	//(select) first exclude the special case that root1 is empty and root2 is empty, and the values of the two nodes are unequal
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        //(sequence) after excluding special cases, when root1=root2, continue to compare its left and right nodes
        return judgeSubTree(root1.left, root2.left) &&
               judgeSubTree(root1.right, root2.right);
    }
}

Substructure
As long as we find a part of the tree nodes that match the tree

Links: https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88?answerType=1&f=discussion
//Source: niuke.com

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return judgeSubTree(root1, root2) ||
               judgeSubTree(root1.left, root2) ||
               judgeSubTree(root1.right, root2);
    }
 
    private boolean judgeSubTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        //When excluding special cases, the child nodes are relatively broad. When the root nodes are not the same, continue to compare the left node and the root node
        if (root1.val != root2.val) {
            return judgeSubTree(root1.left, root2) ||
                   judgeSubTree(root1.right, root2);
        }
        return judgeSubTree(root1.left, root2.left) &&
               judgeSubTree(root1.right, root2.right);
    }
}

It can be found that the substructure is relative to the subtree, only in the judgeSubTree function,

Subtree, when the root node is different, it directly returns false, that is, it is not a subtree

if (root1.val != root2.val) {
            return false;
        }

Substructure, when the root node comparison is different, gives the possibility to continue the comparison

if (root1.val != root2.val) {
            return judgeSubTree(root1.left, root2) ||
                   judgeSubTree(root1.right, root2);
        }