【算法题解】 Day23 搜索与回溯

简介: 今天的算法是 「搜索与回溯」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”

剑指 Offer 26. 树的子结构

题目

剑指 Offer 26. 树的子结构 难度:medium

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

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3  
    / \
   4   5  
  / \  
 1   2
AI 代码解读

给定的树 B:

   4 
  /
 1
AI 代码解读

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

输入: A = [1,2,3], B = [3,1]
输出: false
AI 代码解读

示例 2:

输入: A = [3,4,5,1,2], B = [4,1]
输出: true
AI 代码解读

限制:

0 <= 节点个数 <= 10000
 

方法一:先序遍历

思路

若树 B 是树 A 的子结构,则子结构的根节点可能为树 A 的任意一个节点。因此,判断树 B 是否是树 A 的子结构,需完成以下两步工作:

  1. 先序遍历树 A 中的每个节点 nA;(对应函数 isSubStructure(A, B)
  2. 判断树 A 中 以 nA 为根节点的子树 是否包含树 B 。(对应函数 recur(A, B)

recur(A, B) 函数:

1. 终止条件:

1. 当节点 B 为空:说明树 B 已匹配完成(越过叶子节点),因此返回 true ;
2. 当节点 A 为空:说明已经越过树 A 叶子节点,即匹配失败,返回 false ;
3. 当节点 A 和 B 的值不同:说明匹配失败,返回 false ;
AI 代码解读

2. 返回值:

1. 判断 AB 的左子节点是否相等,即 recur(A.left, B.left) ;
2. 判断 AB 的右子节点是否相等,即 recur(A.right, B.right) ;
AI 代码解读

isSubStructure(A, B) 函数:

  1. 特例处理: 当 树 A 为空  树 B 为空 时,直接返回 false ;
  2. 返回值:  若树 B 是树 A 的子结构,则必满足以下三种情况之一,因此用或 || 连接:

    1. 以 节点 A 为根节点的子树 包含树 B ,对应 recur(A, B)
    2. 树 B 是 树 A 左子树 的子结构,对应 isSubStructure(A.left, B)
    3. 树 B 是 树 A 右子树 的子结构,对应 isSubStructure(A.right, B)

 

解题

Python:

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))
AI 代码解读

Java:

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}
AI 代码解读

 

剑指 Offer 27. 二叉树的镜像

题目

剑指 Offer 27. 二叉树的镜像 难度:easy

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

     4  
   /   \  
  2     7  
 / \   / \  
1   3 6   9
AI 代码解读

镜像输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1
AI 代码解读

示例 1:

输入: root = [4,2,7,1,3,6,9]
输出: [4,7,2,9,6,3,1]
AI 代码解读

限制:

0 <= 节点个数 <= 1000
 

方法一:递归

思路

这是一道很经典的二叉树问题。显然,我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像,那么我们只需要交换两棵子树的位置,即可得到以 root 为根节点的整棵子树的镜像。
 

解题

Python:

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        left = self.mirrorTree(root.left)
        right = self.mirrorTree(root.right)
        root.left, root.right = right, left
        return root
AI 代码解读

Java:

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
AI 代码解读

 

后记

📝 上篇精讲: 【算法题解】 Day22 搜索与回溯
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽,期待你的关注;
👍 创作不易,请多多支持;
🔥 系列专栏: 算法题解
目录
打赏
0
0
0
0
0
分享
相关文章
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
98 62
算法系列之搜索算法-深度优先搜索DFS
|
16天前
|
算法系列之回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
31 4
算法系列之回溯算法
|
19小时前
|
算法系列之回溯算法求解数独及所有可能解
数独求解的核心算法是回溯算法。回溯算法是一种通过逐步构建解决方案并在遇到冲突时回退的算法。具体来说,我们尝试在空格中填入一个数字,然后递归地继续填充下一个空格。如果在某个步骤中发现无法继续填充,则回退到上一步并尝试其他数字。
25 8
算法系列之回溯算法求解数独及所有可能解
|
23天前
|
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
33 1
算法系列之搜索算法-广度优先搜索BFS
|
27天前
|
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
94 1
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等