专栏首页陌无崖知识分享【Go】剑指offer:二叉树子树的判断

【Go】剑指offer:二叉树子树的判断

作者 | 陌无崖

转载请联系授权

题目要求

判断A,B两个二叉树,B是否是A的子树

题目分析

对于这个题,首先我们需要知道二叉树的创建,二叉树的种类有很多,这一题中我们先回顾一下二叉树的基本知识,以二叉查找树为例。

二叉树

二叉树是一种存储数据的结构,有一个根节点,每个结点都有左右指针,指向一个新的结点,称根节点的子节点,而子节点也可以有子节点的树状结构。

二叉查找树

性质

  • 任意结点倘若它的左子树不为空,则左子树上的所有结点的值均小于它的根节点的值。
  • 任意结点倘若它的右子树不为空,则右子树上的所有结点的值均大于它的根节点的值。

二叉查找树的创建 基于上述的性质,我们可以动态的创建一个查找树。步骤如下:

  • 传入一个新结点到一颗二叉树。
  • 如果该二叉树的根节点为空,则将此结点置为根节点。
  • 如果二叉树根节点不为空,则将此节点将根节点的值进行比较。
  • 如果结点的值小于根结点,则继续比较该结点的左结点,直到待比较的结点为空。
  • 同理,如果结点的值大于根结点,则继续比较该结点的右结点,直到待比较的结点为空。

定义一个结点类

type treeNode struct {
    Val   int
    Left  *treeNode
    Right *treeNode
}

定义一个二叉树的类

// 定义一个二叉树类
type binaryTree struct {
    // 根结点
    root *treeNode

创建

func (t *binaryTree) CreateTree(val int) {
    if t.Root() == nil {
        t.SetRoot(treeNode{
            Val:   val,
            Left:  nil,
            Right: nil,
        })
    } else {
        root := t.Root()
        for root != nil {
            if val <= root.Val && root.Left == nil{
                root.Left = &treeNode{val,nil,nil}
                break
            } else if val > root.Val && root.Right == nil {
                root.Right = &treeNode{val,nil,nil}
                break
            } else if val <= root.Val && root.Left != nil {
                root = root.Left
            } else if val > root.Val && root.Right != nil {
                root = root.Right
            }
        }
    }
}

接着我们回到题目分析的思路上,对于判断B树是否是A树的子树,首先应该判断B树的根节点是否存在于A树中,如果存在,则继续判断B树的左右子树,是否和找到的A树中相同根节点的左右子树相同。这是一个基本的思路,接着我们具体看一下步骤:

  • 首先从A树的根节点开始遍历,如果根节点相同,则比较B树的左右结点和A树根结点的左右结点
  • 如果不相同,则遍历A树的左右结点进行比较

代码

func HasSubtree(pRoot1 *treeNode, pRoot2 *treeNode) bool {
    result := false
    if pRoot1 != nil && pRoot2 != nil {
        //找到可以开始比较的根节点
        if pRoot1.Val == pRoot2.Val {
            // 进行比较
            result = DoesTreeHHaveTree2(pRoot1, pRoot2)
        }
        // 开始遍历左节点
        if !result {
            result = HasSubtree(pRoot1.Left, pRoot2)
        }
        // 开始遍历右结点
        if !result {
            result = HasSubtree(pRoot1.Right, pRoot2)
        }
    }
    return result
}
func DoesTreeHHaveTree2(pRoot1 *treeNode, pRoot2 *treeNode) bool {
    if pRoot2 == nil {
        return true
    }
    if pRoot1 == nil {
        return false
    }
    if pRoot1.Val != pRoot2.Val {
        return false
    }
    // 不断的递归左右结点进行比较
    return DoesTreeHHaveTree2(pRoot1.Left, pRoot2.Left) && DoesTreeHHaveTree2(pRoot1.Right, pRoot2.Right)
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 两分钟弄懂对称二叉树

    大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的...

    五分钟学算法
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • 剑指 Offer(C++版本)系列:剑指 Offer 07 重建二叉树

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 牛客网剑指offer java 全部题解

    https://mp.weixin.qq.com/s?__biz=MzI5MzYzMDAwNw==&mid=2247485570&idx=2&sn=bcde8b...

    乔戈里
  • 07. 重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    Zoctopus
  • 每天一道剑指offer-平衡二叉树

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 剑指offer 重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    week
  • 剑指Offer-平衡二叉树

    package Tree; /** * 平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 * 平衡二叉树(Balanced Binary ...

    武培轩
  • 剑指Offer-重建二叉树

    题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

    武培轩
  • 剑指offer:重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    帅地
  • 剑指offer:重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    用户1148523
  • 剑指offer——平衡二叉树

    如果树为空,返回true。否则递归判断每个树节点的其左右子树高度之差的绝对值是否为0或者1,若是返回true,不是返回false。 注明:这里平衡二叉树不需...

    AI那点小事
  • 剑指offer--重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    AI那点小事
  • 剑指 Offer 重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    灰白色
  • 剑指offer 平衡二叉树

    平衡二叉树是这样定义的: 平衡二叉树(Balanced Binary Tree)又被称为AVL树,具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝...

    vincentbbli
  • 每日算法题:Day 9

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    算法工程师之路
  • 剑指offer 二叉树的深度

    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

    week
  • 剑指Offer-二叉树的深度

    package Tree; import java.util.LinkedList; import java.util.Queue; /** * 二叉树...

    武培轩
  • 剑指Offer-二叉树的镜像

    package Tree; import java.util.ArrayDeque; import java.util.ArrayList; import j...

    武培轩

扫码关注云+社区

领取腾讯云代金券