树的子结构

1. 题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

2. 思路

两颗树一起先序遍历

3. 实现

• java

public class 树的子结构
{
    public boolean HasSubtree(TreeNode root1, TreeNode root2)
    {
        //检查参数为空
        if (root1 == null || root2 == null)
        {
            return false;
        }

        return treeEquals(root1, root2)
                //或者 root1左子树包含root2
                || this.HasSubtree(root1.left, root2)
                //或者 root1右子树包含root2
                || this.HasSubtree(root1.right, root2);

    }

    private boolean treeEquals(TreeNode root1, TreeNode root2)
    {
        //root2遍历完了，那么理所当然返回true
        if (root2 == null)
        {
            return true;
        }

        //root2没有遍历完，但是root2居然先空了，那么返回false
        if (root1 == null)
        {
            return false;
        }

        //root1、root2当前节点值相等 并且 root1左子树包含root2左子树 并且 root1右子树包含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
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pRoot1 TreeNode类
 * @param pRoot2 TreeNode类
 * @return bool布尔型
 */
//时间复杂度：O(mn)，m为A树的节点数，n为B树的节点数
func HasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
	if pRoot1 == nil || pRoot2 == nil {
		return false
	}

	//先序遍历
	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. 参考

• 树的子结构_牛客网
• Subtree of Another Tree - LeetCode