18. 树的子结构《剑指Offer》(Java版)

Bertha 。 2022-03-10 13:54 151阅读 0赞

[github][]

## 题目描述 ##

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

/**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。
     * （ps：我们约定空树不是任意一个树的子结构）
     */
    public class _018_HasSubtree {
        /**
         * 几乎所有树的问题都是递归的问题。
         * 对于每个节点都要判断是否与目标子树节点相同。
         */
        public boolean HasSubtree(TreeNode root1, TreeNode subRoot) {
            if (subRoot != null && root1 != null) {
                if (root1.val == subRoot.val) {
                    // 是否是同一个树
                    if (hasSameTree(root1, subRoot)) {
                        return true;
                    }
                }
                // 对每个节点都要进行上述过程。
                return HasSubtree(root1.left, subRoot) || HasSubtree(root1.right, subRoot);
            }
            return false;
        }
    
        private boolean hasSameTree(TreeNode root1, TreeNode root2) {
            if (root2 == null) {
                return true;
            }
            if (root1 == null) {
                return false;
            }
            // 对每个节点都要进行上述过程
            if (root1.val == root2.val) {
                return hasSameTree(root1.left, root2.left) && hasSameTree(root1.right, root2.right);
            }
            return false;
        }
    }

[github]: https://github.com/RudBob/offer66

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer之面试题18树的子结构

问题描述：输入两颗二叉树A和B，判断B是不是A的子结构。实现代码如下： include <stdio.h> include <stdlib.h>

痛定思痛。/ 2022年08月22日 03:49/ 0 赞/ 114 阅读

相关【剑指offer-Java版】18树的子结构

树的子结构：输入两棵二叉树A B，判断B是不是A的子结构就是一个递归加上一个树的先序遍历 public class _Q18 { pub

素颜马尾好姑娘i/ 2022年08月21日 08:58/ 0 赞/ 123 阅读

相关剑指offer_面试题18_树的子结构

题目：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。两个步骤： 1、第一步在树 A 中找到和树 B 的根结点的值一样的结点 R 2、第二步再判断树 A 中

我就是我/ 2022年08月04日 00:46/ 0 赞/ 141 阅读

相关剑指Offer面试题18（Java版）：树的子结构

题目：输入两棵二叉树A和B，判断B是不是A的子结构。例如图中所示的两棵二叉树，由于A中有一部分子树的结构和B 是一样的，因此B是A的子结构。 ![Center][]

╰半夏微凉°/ 2022年07月16日 04:53/ 0 赞/ 140 阅读

相关剑指offer-题18：树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）实验平台：[牛客网][Link 1] -------------

╰+攻爆jí腚メ/ 2022年05月29日 00:56/ 0 赞/ 164 阅读

相关【剑指Offer】18树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）时间限制：1秒；空间限制：32768K 解题思路解题思路

骑猪看日落/ 2022年05月05日 04:27/ 0 赞/ 172 阅读

相关【剑指Offer】（树）树的子结构

题目链接：[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11

一时失言乱红尘/ 2022年03月16日 00:57/ 0 赞/ 160 阅读

相关 18. 树的子结构《剑指Offer》(Java版)

[github][] 题目描述 > 输入两棵二叉树A，B，判断B是不是A的子结构。 > > （ps：我们约定空树不是任意一个树的子结构） /

Bertha 。/ 2022年03月10日 13:54/ 0 赞/ 152 阅读

相关剑指Offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路：看到树，第一个想法就是肯定会用到递归。判断B是不是A的子

冷不防/ 2022年02月26日 02:24/ 0 赞/ 187 阅读

相关剑指offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）算法实现本博客没有写实现思想，但是在算法实现中已经用注释的

客官°小女子只卖身不卖艺/ 2022年02月13日 15:01/ 0 赞/ 211 阅读