剑指Offer 26. 树的子结构-526互联

题目描述：

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

解法思路：

首先这道题很明显是采取递归的形式，整体流程主要分为两步：

找到A树上的某个节点与 B树的根节点相匹配，（如果找不到直接false了）。
第一步找到之后，利用递归依次判断A的左子树与B的左子树是否相等，A的右子树与B的右子树是否相等，左右子树比较取与运算得到最终结果。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if B == nil || A == nil {
        return false
    }
    if dfs(A,B) {
        return true
    }
    return isSubStructure(A.Left,B) || isSubStructure(A.Right,B)

}
func dfs(A *TreeNode, B *TreeNode)bool{
    if B == nil {
        return true
    }
    if A == nil || A.Val != B.Val {
        return false
    }
    return dfs(A.Left,B.Left) && dfs(A.Right,B.Right)
}