剑指Offer（十七）：树的子结构

2017年12月8日15:07:12 8 6,694 °C
摘要

输入两颗二叉树A，B，判断B是不是A的子结构。（PS：我们约定空树不是任意一个树的子结构）。

剑指Offer（十七）：树的子结构

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入两颗二叉树A，B，判断B是不是A的子结构。（PS：我们约定空树不是任意一个树的子结构）。

1、思路

要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根节点的子树是不是包含和树B一样的结构。

这里使用递归的方法即可。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;
        if(pRoot1 != NULL && pRoot2 != NULL){
            if(pRoot1->val == pRoot2->val){
            result = DoesTree1HasTree2(pRoot1, pRoot2);
        }
            if(!result){
                result = HasSubtree(pRoot1->left, pRoot2);
            }
            if(!result){
                result = HasSubtree(pRoot1->right, pRoot2);
            }
        }
        return result;
    }
private:
    bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot2 == NULL){
            return true;
        }
        if(pRoot1 == NULL){
            return false;
        }
        if(pRoot1->val != pRoot2->val){
            return false;
        }
        return DoesTree1HasTree2(pRoot1->left, pRoot2->left) && DoesTree1HasTree2(pRoot1->right, pRoot2->right);
    }
};

Python2.7：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2) or self.is_subtree(pRoot1, pRoot2)
    def is_subtree(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.is_subtree(A.left, B.left) and self.is_subtree(A.right, B.right)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：8   其中：访客  7   博主  1

    • avatar 大敏 来自天朝的朋友 谷歌浏览器 Windows 7 广东省深圳市宝安区 /南山区电信 3
      回复 2018年10月26日 上午8:19  沙发

      我理解错了，不好意思

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口
          回复 2018年10月26日 上午8:22  1层

          @大敏 呃，我这突然一看也感觉错了，哈哈。

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
          回复 2019年4月8日 下午3:13  板凳

          python2.7版
          这个代码和您前面提到的解题思路是一致的吗？感觉不像啊

            • avatar walker 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省西安市 电信 1
              回复 2019年8月22日 下午6:00  1层

              @小小毛 公有函数是找与子树根结点相同的结点，私有函数判断的是根结点相同的两棵树A是否包含B。和作者的分析是一致的。

                • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信通 3
                  回复 2019年8月22日 下午6:15  2层

                  @walker 大意是：判断B是不是A的子结构。也就是B是A的一部分就行或者是B都包含在A中。也即是固定A，挨个检验B是否在A中就行啊

                • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信通 3
                  回复 2019年8月22日 下午6:13  1层

                  @小小毛 判断B是不是A的子结构。也就是B是A的一部分就行或者是B都包含在A中。也即是固定A，挨个检验B是否在A中就行啊。

                    • avatar walker 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省西安市 电信 0
                      回复 2019年8月22日 下午6:21  2层

                      @小小毛 嗯嗯，是的。整个函数就是实现这么一个功能的。我觉得设置的私有函数也就是为了结构化编程，代码更友好吧。

                  • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
                    回复 2019年4月8日 下午4:14  地板

                    明白了，sorray。