Jz-017 – Tree substructure

Substructure of a tree

Topic describes

Enter two binary trees A and B to determine whether B is A substructure of A. (PS: We stipulate that an empty tree is not a substructure of any tree)

Substructure of a tree

code

Enter two binary trees A, B, and determine whether B is A substructure of A. (ps: We agree that the empty tree is not a substructure of any tree.) * https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&&tqId=11170&rp=1&ru=/ta/coding-interviews&qru =/ta/coding-interviews/question-ranking */
public class Jz17 {

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(2);
        TreeNode root2 = new TreeNode(2);

        Jz17 jz17 = new Jz17();
        System.out.println(jz17.hasSubtree(root1, root2));
    }

    public boolean hasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }

        return isSubtreeWithRoot(root1, root2) || hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
    }

    /** * recursion **@param root1
     * @param root2
     * @return* /
    private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if(root1.val ! = root2.val) {return false;
        }
        returnisSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right); }}Copy the code

In short, the years were long, but worth the wait.