Substructure of a Tree

1. Problem Description

Given two binary trees A and B, determine whether B is a substructure of A. (ps: an empty tree is not considered a substructure of any tree.)

2. Approach

Traverse the two trees together in preorder.

3. Implementation

• java

public class 树的子结构
{
    public boolean HasSubtree(TreeNode root1, TreeNode root2)
    {
        // Check empty parameters
        if (root1 == null || root2 == null)
        {
            return false;
        }

        return treeEquals(root1, root2)
                // Or the left subtree of root1 contains root2
                || this.HasSubtree(root1.left, root2)
                // Or the right subtree of root1 contains root2
                || this.HasSubtree(root1.right, root2);

    }

    private boolean treeEquals(TreeNode root1, TreeNode root2)
    {
        // If root2 has been fully traversed, return true
        if (root2 == null)
        {
            return true;
        }

        // root2 has not been fully traversed, but root1 is already empty, so return false
        if (root1 == null)
        {
            return false;
        }

        // The current values of root1 and root2 are equal, the left subtree of root1 contains the left subtree of root2, and the right subtree of root1 contains the right subtree of root2
        return root1.val == root2.val
                && this.treeEquals(root1.left, root2.left)
                && this.treeEquals(root1.right, root2.right);

    }
}

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param pRoot1 TreeNode class
 * @param pRoot2 TreeNode class
 * @return bool
 */
// Time complexity: O(mn), where m is the number of nodes in tree A and n is the number of nodes in tree B
func HasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
	if pRoot1 == nil || pRoot2 == nil {
		return false
	}

	// Preorder traversal
	return isSame(pRoot1, pRoot2) || HasSubtree(pRoot1.Left, pRoot2) || HasSubtree(pRoot1.Right, pRoot2)
}

func isSame(root1 *TreeNode, root2 *TreeNode) bool {
	if root2 == nil {
		return true
	}
	if root1 == nil {
		return false
	}

	return root1.Val == root2.Val && isSame(root1.Left, root2.Left) && isSame(root1.Right, root2.Right)
}

4. References

• Substructure of a Tree - NowCoder
• Subtree of Another Tree - LeetCode