数据结构与算法——搜索与回溯算法（中等）

vlambda
2021-09-24

数据结构与算法——搜索与回溯算法（中等）

由于需要上课，而且这一天的题难度于我而言有点大，所以做了两天才勉强看懂。后面还需要多复习这类题。这类题主要就是利用递归写DFS，DFS、BFS针对的都是二叉树，处理起来各有各自的特点。DFS是一次性搜索到最深处，然后回溯接着横向搜索，所以这种思路就和递归不谋而合，所以大部分DFS都是递归的写法，写起来代码也简捷，就是理解的话需要一定的思考了。

1. 树的子结构

（1）题目

数据结构与算法——搜索与回溯算法（中等）

（2）求解思路

我一开始的思路就是利用DFS遍历A树时，同时判断当前节点是否等于B树的根节点，那么就可以接着判断下去；如果子节点有不同，则说明不正确；如果B树的节点遍历到null后仍没有“不正确返回”，那么就是正确了。但是代码写起来不熟练，没能解决。

官方解析给出的是利用递归：

数据结构与算法——搜索与回溯算法（中等）

算法的流程：

数据结构与算法——搜索与回溯算法（中等）

（3）代码

Python代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: def recur(A,B): if not B: return True# B越界了，即到达了为空的叶子节点->跳出递归，正确 if not A or A.val != B.val: return False# A遍历完了or当前节点值不对的话->跳出递归，不正确 return recur(A.left,B.left) and recur(A.right,B.right)# 当前节点没问题->继续判断左节点和右节点 # 外围递归 # 如果当前节点有一个为None，则直接返回false # 递归判断A,B节点 or 判断A的左子树和B or A的右子树和B        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

2. 二叉树的镜像

（1）题目

数据结构与算法——搜索与回溯算法（中等）

（2）求解思路

这题我是直接看官方解析的了。官方有两种方法，一种递归遍历，也就是DFS，另一种是借助了辅助栈（更容易看懂）。

方法一：递归法

数据结构与算法——搜索与回溯算法（中等）

方法二：辅助栈

数据结构与算法——搜索与回溯算法（中等）

该方法在出栈时每次只出一个节点，且栈的“先入后出”的特性很好地实现了镜像的效果。

（3）代码

递归法的Python代码：

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

由于Python的平行赋值特性，所以这个Python代码十分的简洁。

辅助栈法的Python代码：

class Solution: def mirrorTree(self, root: TreeNode) -> TreeNode: if not root: return stack = [root] while stack: node = stack.pop() if node.left: stack.append(node.left) if node.right: stack.append(node.right) node.left, node.right = node.right, node.left return root

这个方法就看起来比较容易理解了，每次通过堆栈实现左右节点的交换，由于交换节点的同时，该节点所带的子节点也是一起交换的，所以就能达到镜像的要求了。

3. 对称的二叉树

（1）题目

数据结构与算法——搜索与回溯算法（中等）

（2）求解思路

这题有一个思路就是继承上一题的辅助栈法，设定左右节点的两个stack，然后每次判断左右节点需要进一步判断当前左节点的左节点和当前右节点的右节点以及当前左节点的右节点和当前右节点的左节点是否相等，这种写法还是很容易理解的。而LeetCode官方还是给出了更为简洁的递归遍历算法：

数据结构与算法——搜索与回溯算法（中等）

（3）代码

辅助栈法的Python代码：

class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True stack_left ,stack_right = [], [] if (not root.left and root.right) or (not root.right and root.left):# 根节点只存在一个子节点->一定不对称 return False elif root.left and root.left: # 根节点的左右节点均存在，存入堆栈 stack_left.append(root.left) stack_right.append(root.right) else: # root没有左右节点->一定对称 return True while stack_right and stack_left: node_left = stack_left.pop() node_right = stack_right.pop() if node_left.val == node_right.val: # 左右对称节点的值是否相等（值不对称） if node_left.left and node_right.right: # 如果左节点的左节点和右节点的右节点都存在 stack_left.append(node_left.left) stack_right.append(node_right.right) elif node_left.left or node_right.right:# 最少缺失一个节点（结构不对成） return False if node_left.right and node_right.left:# 如果左节点的右节点和右节点的左节点都存在 stack_left.append(node_left.right) stack_right.append(node_right.left) elif node_left.right or node_right.left:# 最少缺失一个节点（结构不对成） return False else: return False return True

递归法的Python代码：

class Solution: def isSymmetric(self, root: TreeNode) -> bool: def recur(L, R): if not L and not R: return True if not L or not R or L.val != R.val: return False return recur(L.left, R.right) and recur(L.right, R.left)
 return not root or recur(root.left, root.right) # 处理刚开始的根节点

LeetCode官方设定这三个题都是“简单”题，说明对于擅长的人来说这并不是什么难题，而我由于一直无法很好地理解递归，且不擅长写好递归，所以还需要多练习这类题。任重而道远！

vlambda博客
学习文章列表