二叉树的子结构
前言
牛客网剑指offer的66道题,刷起来!每道题会提供简单的思路以及测试通过的代码
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
二叉树结构:
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
注:点击左下角的阅读原文即可跳转到原文,可以提交代码
解答思路
对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的,这道题也是。
首先我们先以 A 的根节点 root1 作为起点来判断 B 是否为 A的子结构。 如果是则直接返回 true,如果不是,则递归以 root1.left 和 root1.right 作为起点来判断。代码如下:
public class 树的子结构 { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if (root2 == null || root1 == null) { return false; } // 判断 B 是否为 A 的子结构 return isSubTree(root1, root2); } // 判断 B 是否为 A 的子结构 private boolean isSubTree(TreeNode root1, TreeNode root2) { if (root1 == null) { return false; }// 以root1为root2的根节点,判断子结构是否成立 if (judge(root1, root2)) { return true; } else { // 如果root1作为起点不行,则递归判断左右节点 return isSubTree(root1.left, root2) || isSubTree(root1.right, root2); } } // 以root1为root2的根节点,判断子结构是否成立 private boolean judge(TreeNode root1, TreeNode root2) { if(root2 == null) return true; if(root1 == null) return false; if(root1.val == root2.val) return judge(root1.left, root2.left) && judge(root1.right, root2.right); return false; } }
原文地址:https://www.cnblogs.com/kubidemanong/p/10539350.html
相关推荐
-
如何提高使用Java反射的效率? Java基础
2019-5-17
-
Java多线程同步工具类之Semaphore Java基础
2019-9-6
-
Ansible 入门学习笔记 Java基础
2019-10-2
-
java_方法 Java基础
2019-8-18
-
Android开发常用权限设置 Java基础
2019-5-5
-
web scraper 抓取网页数据的几个常见问题 Java基础
2019-7-25
-
【原创!推荐!】不了解布隆过滤器?一文给你整的明明白白! Java基础
2020-6-13
-
设计更好的Web API Java基础
2019-8-26
-
[JVM教程与调优] 了解JVM 堆内存溢出以及非堆内存溢出 Java基础
2020-7-4
-
工作中常见的五种技术leader Java基础
2019-8-20