剑指Offer对答如流系列 - 树的子结构

栏目: IT技术 · 发布时间: 4年前

内容简介:输入两棵二叉树A和B,判断B是不是A的子结构。二叉树的定义如下:看了看《剑指Offer》高质量代码章节的面试题,发现难度都不高,但是没有分析好边界条件亦或是想当然就是容易出错,细心从来不是说说而已。请重视自己代码的规范性、完整性和鲁棒性。这道题的思路可以概况如下:

文章目录

面试题26:树的子结构

一、问题描述

输入两棵二叉树A和B,判断B是不是A的子结构。二叉树的定义如下:

public class TreeNode{
        double val;
        TreeNode left = null;
        TreeNode right =null;
        public TreeNode(int val) {
            this.val=val;
        }
    }

比如下面的 B是A的子结构

剑指Offer对答如流系列 - 树的子结构

二、问题分析

看了看《剑指Offer》高质量代码章节的面试题,发现难度都不高,但是没有分析好边界条件亦或是想当然就是容易出错,细心从来不是说说而已。请重视自己代码的规范性、完整性和鲁棒性。

这道题的思路可以概况如下:

  1. 先对A树进行遍历,找到与B树的根结点值相同的结点R;
  2. 判断A树中以R为根结点的子树是否包含B树一样的结构。

三、问题解答

// 方法入口,对每个结点遍历判断
    public boolean hasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null) {
            return false;
        }
        return doesTree1HasTree(root1, root2)|| hasSubtree(root1.left, root2)
                ||hasSubtree(root1.right, root2);
    }

    // 判断root结点开始的子树中各个结点是否相同
    private boolean doesTree1HasTree(TreeNode root1,TreeNode root2) {
        if(root2==null) return true;
        if(root1==null) return false;
        return equal(root1.val, root2.val) && doesTree1HasTree(root1.left, root2.left)
                && doesTree1HasTree(root1.right, root2.right);
    }

    // 判断两个浮点数是否相等
    private boolean equal(double num1,double num2) {
        return num1 - num2 < 0.0000001 && num1 - num2 > -0.0000001;
    }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

单元测试之道Java版

单元测试之道Java版

David Thomas、Andrew Hunt / 陈伟柱、陶文 / 电子工业 / 2005-1 / 25.00元

程序员修炼三部曲丛书包含了四本书,介绍了每个注重实效的程序员和成功团队所必备的一些工具。 注重实效的程序员都会利用反馈来指导开发,并驱动个人的开发流程。编码的时候,最有用的反馈来自于“单元测试”。 为了测试一座桥梁,不会只在晴朗的天气,开一辆汽车从桥中间穿过,就认为已经完成了对桥梁的测试。然而许多程序员却正在使用这种测试方法——把这种一次顺利通过称为“测试”。事实上,注重实效的程序员应......一起来看看 《单元测试之道Java版》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具