题解 | #树的子结构#

package main

import . "nc_tools"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pRoot1 TreeNode类
 * @param pRoot2 TreeNode类
 * @return bool布尔型
 */
func HasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
	// write code here
	// 空树不是任意一个树的子结构
	if pRoot2 == nil {
		return false
	}

	// 当 A 树为空节点，但是 B 树还有节点的时候，不为子树
	if pRoot1 == nil && pRoot2 != nil {
		return false
	}

	// 但是 A 树不为空节点，B 树为空节点时可以是子树
	if pRoot1 == nil || pRoot2 == nil {
		return true
	}

	return traverser(pRoot1, pRoot2) || HasSubtree(pRoot1.Left, pRoot2) || HasSubtree(pRoot1.Right, pRoot2)
}

func traverser(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
	if pRoot1 == nil && pRoot2 != nil {
		return false
	}
	if pRoot1 == nil || pRoot2 == nil {
		return true
	}
	if pRoot1.Val != pRoot2.Val {
		return false
	}

	return traverser(pRoot1.Left, pRoot2.Left) && traverser(pRoot1.Right, pRoot2.Right)
}