剑指 Offer 26. 树的子结构

题目描述

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

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

例如:

给定的树 A:

给定的树 B：

   4
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func isSubStructure(A *TreeNode, B *TreeNode) bool {
    return A != nil && B != nil && (recur(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B))
}

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

    return recur(A.Left, B.Left) && recur(A.Right, B.Right)
}