前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer打卡5:二叉树的子结构

剑指offer打卡5:二叉树的子结构

作者头像
帅地
发布2019-03-11 15:48:25
2400
发布2019-03-11 15:48:25
举报
文章被收录于专栏:苦逼的码农

前言

牛客网剑指offer的66道题,刷起来!每道题会提供简单的思路以及测试通过的代码

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

二叉树结构:

代码语言:javascript
复制
1 class TreeNode {
2     int val;
3     TreeNode left;
4     TreeNode right;
5     TreeNode(int x) { val = x; }
6 }

注:点击左下角的阅读原文即可跳转到原文,可以提交代码

解答思路

对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的,这道题也是。

首先我们先以 A 的根节点 root1 作为起点来判断 B 是否为 A的子结构。 如果是则直接返回 true,如果不是,则递归以 root1.left 和 root1.right 作为起点来判断。代码如下:

代码语言:javascript
复制
 1public class 树的子结构 {
 2    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 3        if (root2 == null || root1 == null) {
 4            return false;
 5        }
 6        // 判断 B 是否为 A 的子结构
 7        return isSubTree(root1, root2);
 8    }
 9
10    // 判断 B 是否为 A 的子结构
11  private boolean isSubTree(TreeNode root1, TreeNode root2) {
12      if (root1 == null) {
13          return false;
14      }// 以root1为root2的根节点,判断子结构是否成立
15      if (judge(root1, root2)) {
16          return true;
17      } else {
18          // 如果root1作为起点不行,则递归判断左右节点
19          return isSubTree(root1.left, root2) || isSubTree(root1.right, root2);
20      }
21    }
22    // 以root1为root2的根节点,判断子结构是否成立
23    private boolean judge(TreeNode root1, TreeNode root2) {
24        if(root2 == null)
25            return true;
26        if(root1 == null)
27            return false;
28        if(root1.val == root2.val)
29            return judge(root1.left, root2.left) && judge(root1.right, root2.right);
30
31        return false;
32    }
33}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 题目描述
  • 解答思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档