题目描述

输入两棵二叉树A和B，判断B是不是A的子结构，二叉树的节点定义如下：

/** * 二叉树节点 * */
public class BinaryTreeNode {
   
    double value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

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

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

例如:
给定的树 A:

3 / \ 4 5 / \ 1 2
给定的树 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

测试用例

• 功能测试（树A和树B都是普通的二叉树；树B是或者不是树A的子结构）
• 特殊输入测试（两颗二叉树的一个或者两个根节点为空指针；二叉树的所有节点都没有左子树或者右子树）

题目考点

• 考察应聘者对二叉树的便宜算法的理解及递归编程能力
• 考察应聘者所写代码的鲁棒性

解题思路

class Solution {
   
    public boolean isSubStructure(TreeNode A, TreeNode B) {
   
        return (A != null && B != null) && (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);
    }
}

补充

与二叉树相关的代码有大量的指针操作，在每次使用指针的时候，我们都要问自己这个指针有没有可能是空指针，如果是空指针则该怎么处理。

由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号判断两个小数是否相等。如果两个小数的差的绝对值很小，如小于0.0000001，就可以任务它们相等。

从规范性、完整性和鲁棒性3个方面提高代码质量

• 规范性：书写清晰、布局合理、命名合理
• 完整性：完成基本功能、考虑边界条件、做好错误处理
• 鲁棒性：采取防御性编程、处理无效的输入