树的子结构

题目：

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

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

示例

     3                   4
    / \                /
   4   5              1
  / \
 1   2

    树A                  树B

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

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

思考：

提示

• 先序遍历树 A 中的每个节点

• 判断以树 A 中每个节点为根节点的子树是否包含树 B

题解：

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {

        if (A == null || B == null) return false;

        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    boolean recur(TreeNode A, TreeNode B){

        if (B == null) return true;

        if (A == null || A.val != B.val) return false;

        return recur(A.left, B.left) && recur(A.right, B.right);

    }
}