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

帅地

发布于 2019-03-11 15:48:25

2400

发布于 2019-03-11 15:48:25

文章被收录于专栏：苦逼的码农

前言

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

题目描述

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

二叉树结构：

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 作为起点来判断。代码如下：

 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 删除

二叉树