17 图解剑指Offer 树的子结构 Java题解

灰太狼 2023-02-20 13:45 21阅读 0赞

### 17 图解剑指Offer 树的子结构 Java题解 ###

*  17 图解剑指Offer 树的子结构 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 17 图解剑指Offer 树的子结构 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

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

### 题解: ###

1.判断root1和root2是否为null 如果为null 返回 false。  
2. 返回 check(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)这三个任意一个条件成立，root2即为root1的子结构。(1) check(root1, root2)检查root1的值和root2的值是否相等 (2)HasSubtree(root1.left, root2) 判断 root2是否为root1左子树的子结构，另一个是判断右子树。  
3.实现check();（1）首先判断root2是否为null，如果为null，则代表roo2已匹配完，返回true。  
（2）如果root1 为null root2不为null，肯定不匹配，返回false。  
（3）如果 root1.val = root2.val return check(root1.left, root2.left) &&  
check(root1.right, root2.right) 否则代表值不等，返回false。

4.check的递归终止条件: 如果root2的值一直与root1相等，那么root2.left和root2.right最后为null时代表有子结构，root1.left和right为null代表无子结构。

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            if(root1 == null || root2 == null){ 
                return false;
            }
            return check(root1, root2) || 
                   HasSubtree(root1.left, root2) ||
                   HasSubtree(root1.right, root2);
        }
        public boolean check(TreeNode root1, TreeNode root2){ 
            //要先判断roo2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}这个测试用例通不过。
            if(root2 == null)
                return true;
            if(root1 == null)
                return false;
            if(root1.val == root2.val){ 
                return check(root1.left, root2.left) && 
                    check(root1.right, root2.right);
            }else
                return false;
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1)  
最坏时间复杂度: 递归时间复杂度O( logn)

[Link 1]: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627180243317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

相关树的子结构Java-剑指offer

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路 1、比较根节点val相同，则进行左右节点的比较...

亦凉/ 2024年04月17日 17:27/ 0 赞/ 45 阅读

相关【剑指offer】17树的子结构

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

妖狐艹你老母/ 2023年10月17日 18:46/ 0 赞/ 12 阅读

相关【剑指offer】-树的子结构-17/67

1. 题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 2. 题目分析 ![在这里插入图片描述][waterm

青旅半醒/ 2023年07月22日 09:01/ 0 赞/ 72 阅读

相关 17 图解剑指Offer 树的子结构 Java题解

17 图解剑指Offer 树的子结构 Java题解 17 图解剑指Offer 树的子结构 Java题解题目链接题目描述

灰太狼/ 2023年02月20日 13:45/ 0 赞/ 22 阅读

相关【剑指Offer题解：java】树的子结构

文章目录题目分析代码题目输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构

朴灿烈づ我的快乐病毒、/ 2022年10月25日 04:40/ 0 赞/ 108 阅读

相关 [剑指offer][Java]树的子结构

题目 [https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88][https

落日映苍穹つ/ 2022年05月10日 02:46/ 0 赞/ 99 阅读

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

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

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

相关剑指Offer-树的子结构

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

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

相关剑指offer-树的子结构

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

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

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

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

左手的ㄟ右手/ 2022年01月28日 01:25/ 0 赞/ 161 阅读