剑指offer刷题记录20--树的子结构

该系列博客内容主要是《剑指Offer》中的经典题目,结合在刷题过程中见到的一些精彩的解题过程,从而在这里记录下来。代码以Python3实现。
剑指offer刷题记录20--树的子结构
题目分析

若树 B 是树 A的子结构,则子结构的根节点可能为树 A的任意一个节点。因此,判断树 B是否是树 A的子结构,需完成以下两步工作:
第一步:在树A中找到和树B的根节点的值一样的节点R;
第二步:判断树A中以R为根节点的子树是不是包含和树B一样的结构;

边界条件(终止条件)

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

返回值

  1. 若树A和树B都不为空,则对其节点的值进行判断看是否相等,直到树A,树B所有的左右子节点判断完毕。

特例处理: 当 树 A为空 或 树 B 为空 时,直接返回 false;

代码如下
剑指offer刷题记录20--树的子结构
复杂度分析

时间复杂度:O(MN),其中M,N分别为树A和树B的节点数量;先序遍历树A占用O(M),每次在递归调用判断的时候占用O(N)。
空间复杂度:O(M),当树A和树B都退化为链表的时候,递归调用深度最大。当M≤N时,遍历树A与递归判断的总递归深度为M;当M>N时,最差情况为遍历至树A叶子节点,此时总递归深度为M。

参考链接1
思路清晰的DFS
剑指offer刷题记录20--树的子结构
该解法比较容易理解,但是不太明白这里的result = false是什么意思。

深度优先搜索