内容简介:输入两棵二叉树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》高质量代码章节的面试题,发现难度都不高,但是没有分析好边界条件亦或是想当然就是容易出错,细心从来不是说说而已。请重视自己代码的规范性、完整性和鲁棒性。
这道题的思路可以概况如下:
- 先对A树进行遍历,找到与B树的根结点值相同的结点R;
- 判断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; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
编程之美:微软技术面试心得
《编程之美》小组 / 电子工业出版社 / 2018-9 / 79
《编程之美:微软技术面试心得》收集了约60道算法和程序设计的题目,这些题目大部分在微软的笔试、面试中出现过,有的曾被微软员工热烈地讨论过。作者试图从书中各种有趣的问题出发,引导读者发现问题、分析问题、解决问题,寻找更优的解法。《编程之美:微软技术面试心得》内容分为以下几个部分。 游戏之乐:从游戏和其他有趣问题出发,化繁为简,分析总结。 数字之魅:编程的过程实际上就是和数字及字符打交道的......一起来看看 《编程之美:微软技术面试心得》 这本书的介绍吧!
随机密码生成器
多种字符组合密码
UNIX 时间戳转换
UNIX 时间戳转换