CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

    • 二叉树理论基础
    • 二叉树的四种遍历方法
    • 如何构造一棵二叉树
    • 序列化与反序列化二叉树
    • 左叶子之和
    • 找树左下角的值
    • 二叉树每层的最大值
    • 二叉树的右侧视图
    • 二叉树的锯齿形层序遍历
    • 翻转二叉树
    • 合并二叉树
    • 二叉树剪枝
    • 对称二叉树
    • 另一棵树的子树
    • 剑指 Offer 26 - 树的子结构
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 寻找重复的子树
    • 二叉树的最大深度
    • 二叉树的最小深度
    • 二叉树的最大宽度
    • 完全二叉树的节点个数
    • 往完全二叉树添加节点
    • 二叉树的完全性检验
    • 平衡二叉树
    • 二叉树的最近公共祖先
    • 最大二叉树
    • 从中序与后序遍历序列构造二叉树
    • 从前序与中序遍历序列构造二叉树
    • 节点之和最大的路径
    • 二叉树的直径
    • 二叉搜索树

    • TreeSet 和 TreeMap

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 二叉树
小牛肉
2022-10-04
目录

剑指 Offer 26 - 树的子结构

# 📃 题目描述

题目链接:剑指 Offer 26. 树的子结构 (opens new window)

# 🔔 解题思路

乍一看和 572. 另一棵树的子树 (opens new window) 好像是一样的,但其实子树和子结构是不同的!

举个例子:

所谓 root2 是否是 root1 的子结构,其实就是从 root2 开始遍历,对应的从 root1 开始,从否匹配到 root2 上的所有节点。

所以这道题其实是一道 DFS 问题~

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }

        // 先从根节点判断 B 是不是 A 的子结构,如果不是在分别从左右两个子树判断,
        // 只要有一个为true,就说明 B 是 A 的子结构
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    // dfs 判断 root2 是否是以 root1 为根节点的树的子结构
    // 就是从 root2 开始遍历,对应的从 root1 开始,从否匹配到 root2 上的所有节点
    private boolean dfs(TreeNode root1, TreeNode root2) {
        // 当节点 B 为空:说明树 B 已匹配完成(越过叶子节点),因此返回 true
        if (root2 == null) {
            return true;
        }
        // 当节点 A 为空:说明已经越过树 A 叶子节点,即匹配失败,返回 false
        // 或者 A.val != B.val,匹配失败,返回 false
        if (root1 == null || root1.val != root2.val) {
            return false;
        }
        
        // 当前节点比较完之后还要继续判断左右子节点
        return dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
另一棵树的子树
寻找重复的子树

← 另一棵树的子树 寻找重复的子树→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式