树的子结构

题目描述

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

这道题目的思路很清晰，

遍历A寻找B的根节点，若不存在则返回false；

                                       若存在则比较找到的这个节点的子树与根节点的子树，若相同则返回true；

                                                                                                                                           若不相同则继续遍历A寻找B的根节点。

由于涉及到树，一般要用到递归来解决。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
         boolean result = false;
        if(root1 != null && root2 != null) {
               if(root1.val == root2.val)//找到相同节点后进行子树判断
                   result = Find(root1, root2);
               if(result == false)//没有找到相同节点，在左子树中继续寻找
                   result = HasSubtree(root1.left, root2);
               if(result == false)//没有找到相同节点，在右子树中继续寻找
                   result = HasSubtree(root1.right, root2);
        }
      return result;
    }

    public boolean Find(TreeNode root1, TreeNode root2) {
            if(root2 == null) return true;//结束条件，标志着遍历结束
            if(root1 == null) return false;//重要，鲁棒性保证
            boolean result = false;
            if(root1 != null && root2 != null) {
                   if(root1.val == root2.val) {
                           //需左子树和右子树均相等才能返回true
                       result = Find(root1.left, root2.left) & Find(root1.right, root2.right);
                   }
            }
            return result;
    }
}

思路很简单，但是需要注意的是，在涉及到树的操作时要高度警惕，每一处需要访问地址的时候均要检查是否为null，若为null应该怎样操作！

写完程序需要自己通过用例检测，经典用例包括：
1、两树根节点有一个或两个为空
2、树A和树B只有左子节点或右子节点
3、树A和树B的节点中含有分叉

这道题目与剑指 offer上的略有不同，这里节点值为int，而剑指 offer上为double。
这里涉及到计算机储存小数存在误差的问题。

先讲一下计算机中小数的存储：
计算机中小数以二进制（浮点数）形式存储。
首先是一个十进制小数形式，转化成二进制的计算案例。
————————————————————————————————
0.8125 转换成二进制

image

其实这种情况是赶巧了得到一个确切的值。

而有两种情是会产生误差的：
1、以二进制保存浮点数，所以一些原本有限位的小数，按照上面方法运算以后，可能变成一个无限循环的小数。
例如：（十进制）0.9转成2进制是无限循环小数0.1110011001100110011...
2、计算机保存浮点数的精度有限，例如float可以保留十进制最多7位（二进制23位）有效数字，double 可以保留十进制15~16位（二进制52位）有效数字。那有效数字以后的就被忽略了。

所以，计算机中保存的小数是存在误差的，不准确的。那么对float和double类型进行比较时便不能使用＝＝，而应该判断它们的差值的绝对值是不是在允许的范围内，若差值很小则可以认为二者相等。
例如：

if((num1 - num2) > -0.0000001 && (num1 - num2) < 0.0000001)
    return true;
else
    return false;