树的子结构.md

题目描述

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

/**
 * 二叉树节点
 *
 * @Author rex
 * 2018/8/1
 */
public class BinaryTreeNode {
    double value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

测试用例

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

题目考点

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

解题思路

代码自明（递归的方式）

自己解题

/**
 * 树的子结构
 * 递归
 *
 * @Author rex
 * 2018/8/1
 */
public class Solution {
    /**
     * 判断树1是否存在树2这样的子树
     * @param root1
     * @param root2
     * @return
     */
    public boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }

        return doesTree1HaveTree2(root1, root2) || doesTree1HaveTree2(root1.left, root2) || doesTree1HaveTree2(root1.right, root2);

    }

    /**
     * 判断树1是否存在树2这样的子树核心
     * @param root1
     * @param root2
     * @return
     */
    public boolean doesTree1HaveTree2(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (equal(root1.value, root2.value)) {
            return doesTree1HaveTree2(root1.left, root2.left) && doesTree1HaveTree2(root1.right, root2.right);
        }
        return false;
    }

    /**
     * 判断两个double类型是否相等
     * @param i
     * @param j
     * @return
     */
    public boolean equal(double i, double j) {
        if (Math.abs(i-j) < 0.0000001) {
            return true;
        } else {
            return false;
        }
    }
}

参考解题

参考自己解题

补充

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

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

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

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