剑指 Offer 26. 树的子结构

题目

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

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

例如: 给定的树 A:

graph TB
3((3)) --- 4((4))
3 --- 5((5))
4 --- 1((1))
4 --- 2((2))

给定的树 B：

graph TB
4((4)) --- 1((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

题解

public boolean isSubStructure(TreeNode A, TreeNode B) {
    // 空树不是任何树的子树
    if (A == null || B == null) {
        return false;
    }

    BiFunction<TreeNode, TreeNode, Boolean> recursion = new BiFunction<TreeNode, TreeNode, Boolean>() {
        @Override
        public Boolean apply(TreeNode a, TreeNode b) {
            // 子树已经比较完成
            if (b == null) {
                return true;
            }

            if (a == null) {
                return false;
            }

            // 比较节点值是否一致以及左右树节点是否一致
            return a.val == b.val && this.apply(a.left, b.left) && this.apply(a.right, b.right);
        }
    };

    // 若值不一致 在A左树或右树上查找
    return recursion.apply(A, B) || this.isSubStructure(A.left, B) || this.isSubStructure(A.right, B);
}