剑指Offer-树的子结构

冷不防 2022-02-26 02:24 186阅读 0赞

## 题目描述 ##

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

解题思路：看到树，第一个想法就是肯定会用到**递归**。判断B是不是A的子结构，**切入点**就是先要找到A中有没有节点能匹配上B的根节点，在接下去判断B的左右子树在不在A中。  
解题思路—**精简**：这个代码内容其实和上述解题思路是一样的！不过，代码简洁了很多！巧妙利用了逻辑运算符：||只要遇到true最后结果则为true，后续条件不再执行；&&只要遇到false最后结果就为false，后续条件也不执行。这个操作极大的精简了代码，但是对于思路不太理解的童鞋来说，还是采用第一种解题思路代码，能更清晰的理解思路。

**注意**：看到有一些童鞋的解法是将树A和树B进行先序遍历，再做字符串匹配。但是因为节点的个数不同，遍历出来的字符串的顺序会发生很大的变化。举个例子：A：\{8,8,7,9,2,\#,\#,\#,\#,4,7\}，B：\{8,8,7\}，B为A的子树，是以A的根节点开始的满二叉树。但是先序遍历后A为8892477，B为887，无法匹配，这个做法行不通，可能是测试用例较少，所以代码能通过，但是思路并不完善。

## Java解题 ##

/**
    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) {
            boolean result = false;
            // 查询root1中是否包含root2根节点
            if(root1!=null && root2!=null){
                if(root1.val==root2.val)
                    result = Judge(root1, root2);
                if(!result)
                    result = HasSubtree(root1.left, root2);
                if(!result)
                    result = HasSubtree(root1.right, root2);
            }
            return result;
        }
        // 判断是否root1中包含root2的其余元素
        public boolean Judge(TreeNode root1, TreeNode root2){
            // root2遍历完了
            if(root2==null)
                return true;
            // root1遍历完了，但是root2没遍历完
            if(root1==null)
                return false;
            if(root1.val!=root2.val)
                return false;
    
            return Judge(root1.left, root2.left) && Judge(root1.right, root2.right);
        }
    }

## Java解题—精简 ##

public class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            // 查询root1中是否包含root2根节点
            if(root1!=null && root2!=null)
                return Judge(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
            // root1或root2中有null
            return false;
        }
        // 判断是否root1中包含root2的其余元素
        public boolean Judge(TreeNode root1, TreeNode root2){
            /// root2遍历完了
            if(root2==null)
                return true;
    
            return !(root1==null) && root1.val==root2.val && Judge(root1.left, root2.left) && Judge(root1.right, root2.right);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关剑指Offer-树的子结构

树的子结构题目描述　　输入两颗二叉树A，B，判断B是不是A的子结构。解题思路：　　先判断A的根结点是否与B的树根相同，若相同，则遍历B的同时遍历A,判

怼烎@/ 2022年08月04日 13:34/ 0 赞/ 138 阅读

相关剑指Offer | 树的子结构

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

灰太狼/ 2022年05月24日 14:13/ 0 赞/ 142 阅读

相关剑指Offer-树的子结构

这道题题目的思路总结： 1）二叉树B当前节点值等于二叉树A当时节点值，则递归地去匹配B的左子树和A的左子树，B的右子树和A的右子树 2）二叉树B当前节点值不等于二叉树A

╰+哭是因爲堅強的太久メ/ 2022年05月22日 23:36/ 0 赞/ 165 阅读

相关剑指offer:树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） AC C++ Solution: 递归: class

我会带着你远行/ 2022年04月10日 07:56/ 0 赞/ 174 阅读

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

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

一时失言乱红尘/ 2022年04月10日 04:20/ 0 赞/ 146 阅读

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

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

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

相关剑指Offer-树的子结构

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

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

相关剑指offer|树的子结构

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

素颜马尾好姑娘i/ 2022年02月16日 16:11/ 0 赞/ 184 阅读

相关剑指offer-树的子结构

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

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

相关剑指offer：树的子结构

试题：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）代码：按照正常思维，我们都知道要一个个搜搜树的节点，每到一个节

妖狐艹你老母/ 2021年09月16日 16:26/ 0 赞/ 305 阅读