题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
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) }