题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

树A：

     8
    / \
   8   7
  / \
 9   2
    / \
   4   7
树B：

   8
  / \
 9   2
返回 true ,因为B是A的子结构。

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
    if pRoot1 == nil || pRoot2 == nil {
        return false
    }
    if same(pRoot1,pRoot2) {
        return true
    }
    return hasSubtree(pRoot1.Left,pRoot2) || hasSubtree(pRoot1.Right,pRoot2)
}

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