美文网首页剑指Offer
剑指Offer-树的子结构

剑指Offer-树的子结构

作者: Codeapes | 来源:发表于2020-02-07 22:30 被阅读0次

1.题目

输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。

2.示例

树 A

     3
    / \
   4   5
  / \
 1   2

树B

   4 
  / \
 1   2

上面 B 是 A 的子结构,故返回 true

3.解题思路

1.在树 A 中找到和树 B 的根结点的值一样的结点 Root。
2.接着判断树 A 中以 Root 为根结点的子树是否包含和树 B 一样的结构。
3.若第 2 步有相同的结构则返回ture,若没有,则继续重复第 1、2步,直到遍历完树 A 还没有找到,就返回false

4.代码实现

#include <stdio.h>
#include <stdbool.h>

// 二叉树的二叉链表存储结构
typedef struct BiTNode {
    double data;                // 结点数据域
    struct BiTNode* lchild;     // 左孩子结点
    struct BiTNode* rchild;     // 右孩子结点
}BiTNode;

// 函数声明
// 不想写声明的话,下面这两个函数的定义需要放到 HasSubTree函数的前面
bool DoesRootAHaveRootB(BiTNode* RootA, BiTNode* RootB);
bool Equal(double num1, double num2);

// 判断树 B 是不是树 A 的子结构
// 主要是通过递归的方式前序遍历树 A,找到一个与树 B 的根结点相等的结点
bool HasSubTree(BiTNode* RootA, BiTNode* RootB)
{
    bool result = false;

    if (RootA != NULL && RootB != NULL) {
        // 若树 A 的某一结点的值和树 B 的头结点的值相同
        if (Equal(RootA->data, RootB->data)) {
            result = DoesRootAHaveRootB(RootA, RootB);
        }

        if (!result) {
            result = HasSubTree(RootA->lchild, RootB);
        }

        if (!result) {
            result = HasSubTree(RootA->rchild, RootB)
        }
    }
    return result;
}

// 判断树 A 中以 Root 为根结点的子树是否和树 B 具有相同的结构
bool DoesRootAHaveRootB(BiTNode* RootA, BiTNode* RootB)
{
    if (RootB == NULL) {
        return true;
    }

    if (RootA == NULL) {
        return false;
    }

    if (!Equal(RootA->data, RootB->data)) {
        return false;
    }

    // 在根结点相同的情况下,若树 A 与 树 B 对应的子结点也都相同,则返回 true
    return DoesRootAHaveRootB(RootA->lchild, RootB->lchild) && 
           DoesRootAHaveRootB(RootA->rchild, RootB->rchild);
}

// 判断两个结点的值是否相等
// 注意判断两个小数是否相等,不能直接用 ==,因为计算机内表示小数时其实都是有误差的
// 因此,一般来说它们之差的绝对值若在一个很小的范围内,就认为它们相等
bool Equal(double num1, double num2)
{
    if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
        return true;
    } else {
        return false;
    }    
}

个人主页:

www.codeapes.cn

相关文章

  • 剑指offer-树的子结构

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

  • 剑指Offer-树的子结构

    1.题目 输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。 2.示例 树 A 树B 上面 B 是 A ...

  • 剑指offer-树

  • [剑指offer] 树的子结构

    题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 递...

  • 【剑指26】树的子结构

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

  • 【剑指 offer】树的子结构。

    1、题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。 我们规定空树不是任何树的子结构。 样例树A8/ \...

  • 剑指offer——树的子结构

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

  • 剑指offer - 树的子结构

    题目 输入两棵二叉树A和B,判断B是不是A的子结构。二叉树节点的定义如下: 下图中的二棵二叉树,由于A中有一部分子...

  • [剑指Offer]树的子结构

    本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...

  • Leetcode-155Min Stack

    155. Min Stack && 剑指offer-包含min函数的栈 Design a stack that s...

网友评论

    本文标题:剑指Offer-树的子结构

    本文链接:https://www.haomeiwen.com/subject/nmxbxhtx.html