【一刷《剑指Offer》】面试题 18:树的子结构

简介: 【一刷《剑指Offer》】面试题 18:树的子结构

核心考点:二叉树理解,二叉树遍历。


一、《剑指Offer》对应内容


二、分析问题

二叉树都是递归定义的,所以递归操作是比较常见的做法。

首先明白:子结构怎么理解,可以理解成子结构是原树的子树(或者一部分)。也就是说,B 要是 A 的子结构,那么 B 的根节点+左子树+右子树都得在 A 中存在且构成树形结构。

比较的过程要分为两步:

  1. 先确定比较的起始位置。
  2. 在确定从该位置开始,在比较其左右子树的内容是否一致。

三、代码

//力扣AC代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasSubtree(TreeNode* a, TreeNode* b)
    {
        if(b==NULL) return true;
        if(a==NULL) return false;
        if(a->val!=b->val) return false;
        return hasSubtree(a->left, b->left) && hasSubtree(a->right, b->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL || B==NULL) return false;
        bool result=false;
        if(A->val==B->val)
            result=hasSubtree(A, B);
        if(!result)
            result=isSubStructure(A->left, B);
        if(!result)
            result=isSubStructure(A->right, B);
        return result;
    }
};
 
//牛客AC代码
/*
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) :
      val(x), left(NULL), right(NULL) {
  }
};*/
class Solution {
public:
  bool isSubStructure(TreeNode* a, TreeNode* b)
  {
    if(b==nullptr) return true;
    if(a==nullptr) return false;
    if(a->val!=b->val) return false;
    return isSubStructure(a->left, b->left) && isSubStructure(a->right, b->right);
  }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    if(pRoot1==nullptr || pRoot2==nullptr) return false;
    bool result=false;
    if(pRoot1->val==pRoot2->val)
      result=isSubStructure(pRoot1, pRoot2);
    if(!result)
      result=HasSubtree(pRoot1->left, pRoot2);
    if(!result)
      result=HasSubtree(pRoot1->right, pRoot2);
    return result;
    }
};


相关文章
|
24天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
24天前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
24天前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
24天前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
24天前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
24天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
24天前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
24天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
24天前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
|
24天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点