Java另一棵树的子树

男娘i 2024-02-24 08:13 9阅读 0赞

**目录**

1.题目描述

2.题解

思路分析

具体实现

完整代码

--------------------

## 1.题目描述 ##

给你两棵二叉树 **`root`**和 **`subRoot`** 。检验 **`root`** 中是否包含和 **`subRoot`**具有相同结构和节点值的子树。如果存在，返回**`true`** ；否则，返回 **`false`**。

二叉树**`tree`**的一棵子树包括 **`tree`**的某个节点和这个节点的所有后代节点。**`tree`**也可以看做它自身的一棵子树。

**示例：**

![1a3d900dbb6e4a999b8b87ea7e4dd4d6.png][]

> **输入：**root = \[3, 4, 5, 1, 2\]，subRoot = \[4, 1, 2\]
> 
> **输出：**true

## 2.题解 ##

### **思路分析** ###

我们首先判断两棵二叉树是否相同，若相同，则subRoot是root的子树；

若不相同，则判断root的左子树是否与subRoot是否相同，若相同，则subRoot是root的子树；

若不同，判断root的右子树是否与subRoot相同，若相同，subRoot是root的子树；

若不同，继续递归判断...

### **具体实现** ###

**1.首先实现判断两棵二叉树是否相同的代码：**

（1）若两棵二叉树都为空，则两颗二叉树相同；若两颗二叉树中只有一棵树为空，则不同

（2）若两棵二叉树都不为空，再判断其根节点的值是否相同，若不相同，两棵二叉树不相同；若相同，再分别判断两颗二叉树的左子树是否相同，右子树是否相同。（通过递归实现）

**具体过程：**

![6b3509f792be4e7e86ab8340c7e08a40.png][]

**代码实现：**

public boolean isSameTree(TreeNode p, TreeNode q) {
        //都为null，相同
        if(p == null && q == null){
            return true;
        }
        //只有一个为null，不同
        if(p == null||  q == null){
            return false;
        }
        //都不为空，但值不为空，不同
        if(p.val != q.val){
            return false;
        }
        //判断两颗二叉树的左子树、右子树是否相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

**2.判断subRoot是否为root子树**

（1）若subRoot为空，则subRoot为root的子树，返回true

（2）若root为空，则subRoot不为root的子树。返回false

（1）判断subRoot是否与root相同

（2）判断subRoot是否是root的左子树

（3）判断subRoot是否是root的右子树

若都不相同，最后返回false

**具体过程：**

**![eed4aa849458435388798ada76ad780f.png][]**

**代码实现：**

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot == null){
            return true;
        }
        if(root == null) {
            return false;
        }
        //1、是不是和根节点相同
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //2、判断是不是root的左子树
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        //3、右子树
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        //4、返回
        return false;
    }

### **完整代码** ###

class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
    
            if(p == null && q == null){
                return true;
            }
            if(p == null||  q == null){
                return false;
            }
            if(p.val != q.val){
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if(subRoot == null){
                return true;
            }
            if(root == null) {
                return false;
            }
            //1、是不是和根节点相同
            if(isSameTree(root,subRoot)) {
                return true;
            }
            //2、判断是不是root的左子树
            if(isSubtree(root.left,subRoot)) {
                return true;
            }
            //3、右子树
            if(isSubtree(root.right,subRoot)) {
                return true;
            }
            //4、返回
            return false;
        }
    }

**题目来自：**

[572. 另一棵树的子树 - 力扣（LeetCode）][572. _ - _LeetCode]

[1a3d900dbb6e4a999b8b87ea7e4dd4d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/af2e24c241c34605890d5cf25136538c.png
[6b3509f792be4e7e86ab8340c7e08a40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/79699371cfc944e6822b542a53739965.png
[eed4aa849458435388798ada76ad780f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/0724695edebd4e0bb35a9b52d2f205f9.png
[572. _ - _LeetCode]: https://leetcode.cn/problems/subtree-of-another-tree/description/

发表评论取消回复

表情：

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

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

相关阅读

相关《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树

力扣刷题笔记——二叉树

一时失言乱红尘/ 2024年04月23日 15:39/ 0 赞/ 29 阅读

相关判断一棵树是否是另一棵树的子树（Java实现）

前面一篇文章介绍了如何判断两棵树相等，思路就是遍历每个节点，然后判断是否均相等，需要用递归来实现。如果需要判断一棵树是另一棵树的子树，该怎么办呢？我们需要借助前面的...

谁借莪１个温暖的怀抱￠/ 2024年04月19日 16:32/ 0 赞/ 44 阅读

相关【Leetcode】965. 单值二叉树、100. 相同的树、572. 另一棵树的子树

> 作者：一个喜欢猫咪的的程序员 > > 专栏：《Leetcode》 > > 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》 > > ![d62cff

淡淡的烟草味﹌/ 2024年03月30日 11:39/ 0 赞/ 38 阅读

相关 LeetCode-572. 另一棵树的子树

题目来源 [572. 另一棵树的子树][572.] 解题思路看到题目描述，首先判断一个树是否是另一棵树的子树，很明显想到可以用递归，但是两棵树完全相同也可以看做一

柔情只为你懂/ 2024年03月27日 15:55/ 0 赞/ 49 阅读

相关 java判断一棵二叉树是另一棵二叉树的子树

判断一棵二叉树是另一棵二叉树的子树题目描述给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子

àì夳堔傛蜴生んèń/ 2024年03月16日 10:51/ 0 赞/ 65 阅读

相关 Java另一棵树的子树

目录 1.题目描述 2.题解思路分析具体实现完整代码 -------------------- 1.题目描述给你两棵二叉树 `root`和 `sub

男娘i/ 2024年02月24日 08:13/ 0 赞/ 10 阅读

相关 Leetcode 572. 另一棵树的子树

题目重述给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回

Myth丶恋晨/ 2022年09月16日 11:24/ 0 赞/ 128 阅读

相关 572 另一棵树的子树（树的哈希）

1. 问题描述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，

以你之姓@/ 2022年08月31日 11:06/ 0 赞/ 141 阅读

相关判断树为另一树的子结构

输入两棵二叉树 A 和 B，判断树 B 是不是 A 的子结构。例如，下图中的两棵树 A 和 B，由于 A 中有一部分子树的结构和 B 是一样的，因此 B 就是 A

缺乏、安全感/ 2022年08月08日 00:58/ 0 赞/ 134 阅读

相关如何判断一棵树是不是另一棵树的子树

给你两棵树，怎么判断一棵树是另一棵树的子树？树1：树2: 1 2 / \\ / \\ 2 3 4 5 / \\ \\ 4 5 7 第一步

红太狼/ 2022年06月07日 23:46/ 0 赞/ 212 阅读