刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

提示：

• 0 <= 节点个数 <= 10000

思路

做完才发现之前已经做过了，不过既然做了就记录下来吧，再整一道别的加个餐

解题思路没什么要说的，就是一个递归

但是有个想法想分享下：
开始我是想着既然做过了，就尝试下新想法，也就是不开 isSub 这个子函数。正好有 LeetCode 这个强大的测试样本。

但是尝试了几次运行之后发现不大可行，函数越来越臃肿，分支处理越来越多，而且情况杂糅之后的心智负担也是陡增...

然后这个时候就联想到了业务里的一大坨超级函数，没人愿意接手维护也是类似情况吧
PS. 当然，防御性编程另说（手动狗头

代码

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}

    // 以传入两节点均为根结点进行判断
	var isSub func(A *TreeNode, B *TreeNode) bool
	isSub = func(A *TreeNode, B *TreeNode) bool {
		if B == nil {
			return true
		} else if A != nil && B != nil {
			if A.Val == B.Val {
				return isSub(A.Left, B.Left) && isSub(A.Right, B.Right)
			}
		}
		return false
	}
    // 需要判断A的子节点为根结点的情况
	return isSub(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}