文档章节

判断子树

a_xianyu
 a_xianyu
发布于 2017/04/09 15:29
字数 283
阅读 40
收藏 0

对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点AB,请返回一个bool值,代表A中是否存在一棵同构于B的子树。

解析:表面上看是一个二叉树的问题,其实转化为字符串问题更加简单

    可以先将二叉树序列化,然后判断是否为字串即可。

    程序中serialize(TreeNode root)适用于二叉树序列化的函数,采用递归实现,简单明了。

    注意:子树的意思是包含了一个节点,就得包含这个节点下的所有结点

             子结构的意思是包含了一个节点,可以只取左子树或只取右子树,或者都不取

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class IdenticalTree {
    public boolean chkIdentical(TreeNode A, TreeNode B) {
        return serialize(A).indexOf(serialize(B)) != -1 ? true : false;
    }
    public String serialize(TreeNode root) {
        if (root == null) {
            return "# ";
        } 
        return root.val + " " + serialize(root.left) + serialize(root.right); 
    }
}

 

© 著作权归作者所有

a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员
私信 提问
LeetCode572. Subtree of Another Tree (另一个棵树的子树)

原题 Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a no......

dby_freedom
2018/12/18
0
0
101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1 / 2 2 / / 3 4 4 3 But the following ......

qdqade
2018/06/26
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
[剑指offer] 树的子结构

题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 递归思想,如果根节点相同则递归调用IsSubtree(),如果根节点不相同,则判断的左...

繁著
2018/06/29
0
0
[剑指offer] 平衡二叉树

本文首发于我的个人博客:尾尾部落 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路 定义:平衡二叉查找树,简称平衡二叉树。 可以是空树。 假如不是空树,任何一个结点的...

繁著
2018/08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud中Hystrix 线程隔离导致ThreadLocal数据丢失

在Spring Cloud中我们用Hystrix来实现断路器,Zuul中默认是用信号量(Hystrix默认是线程)来进行隔离的,我们可以通过配置使用线程方式隔离。 在使用线程隔离的时候,有个问题是必须要解决的...

xiaomin0322
35分钟前
2
0
使用 Jenkins + Ansible 实现 Spring Boot 自动化部署101

本文首发于:Jenkins 中文社区 本文要点: 设计一条 Spring Boot 最基本的流水线:包括构建、制品上传、部署。 使用 Docker 容器运行构建逻辑。 自动化整个实验环境:包括 Jenkins 的配置,J...

Jenkins中文社区
40分钟前
2
0
springcloud配置中心和消息总线,学习,记录其中的问题

改造配置中心的客户端,接入消息总线 1.增加pom文件的引用 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20......

夜中孤影
53分钟前
3
0
gzip压缩

tar -zcvf gz包路径 被压缩的路径 tar -zcvf /home/xxx/test.tar.gz hello gz包的路径可以是 完整的也可以相对 , 被压缩的路径 不要全路径 不然压缩包里也会有全路径...

shzwork
59分钟前
3
0
rancher-1

部署rancher 官方快速部署 https://www.cnrancher.com/quick-start/ 部署命令 mkdir /data/rancher -p# 建立存放rancher数据的目录sudo docker run -d --restart=unless-stopped -v /dat......

以谁为师
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部