• 🏡
    首页
  • 📎
    归档
  • ✍
    日志
  • 🐂
    留言板
顶 峰 相 见
顶 峰 相 见

dfxj

各自努力,顶峰相见

05月
23
算法

另一个树的子树

发表于 2020-05-23 • 被 200 人看爆

题目描述

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2

给定的树 t:

   4 
  / \
 1   2

返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

解题思路

递归

展示树的递归之美🙃
一棵树是另一个棵树的子树,要么两棵树相同,要么一棵树是另一棵树的左子树或者右子树的子树。

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;   // t 为 null 一定都是 true
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null,肯定是 false
        return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
    }
    /**
     * 判断两棵树是否相同
     */
    public boolean isSameTree(TreeNode s, TreeNode t){
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }

其他思路

遍历

先序遍历s, 然后判断每个节点为根的树是否和t相同。

DFS暴力匹配

DFS 序列上做串匹配

分享到:
图的理论基础
二叉树遍历
  • 文章目录
  • 站点概览
dfxj

trade what you see, not what you think

Github QQ Email RSS
看爆 Top5
  • 金融交易技术分析 1,243次看爆
  • Angular 变更检测 —— 它到底是如何工作的? 1,207次看爆
  • kubernetes低版本java客户端ProcessorListener容量问题 1,113次看爆
  • Angular SSR踩坑记录 1,071次看爆
  • kubernetes容器编排和调度管理 1,007次看爆

站点已萌萌哒运行 00 天 00 小时 00 分 00 秒(●'◡'●)ノ♥

Copyright © 2021 dfxj