北大硕士LeetCode算法专题课--递归和回溯

浅浅的花香味﹌ 2024-03-29 14:07 66阅读 0赞

**算法专题课**

[  
  
北大硕士LeetCode算法专题课-栈、队列相关问题\_骨灰级收藏家的博客-CSDN博客][_LeetCode_-_-CSDN]

[北大硕士LeetCode算法专题课--链表相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_--_-CSDN]

[北大硕士LeetCode算法专题课-查找相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN]

[北大硕士LeetCode算法专题课-字符串相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 1]

[北大硕士LeetCode算法专题课-数组相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 2]

[北大硕士LeetCode算法专题课-基础算法查找\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 3]

[北大硕士LeetCode算法专题课-基础算法之排序\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 4]

[北大硕士LeetCode算法专题课---算法复杂度介绍\_骨灰级收藏家的博客-CSDN博客][LeetCode_---_-CSDN]

**二叉树简****介**

二叉树(Binary Tree) 是一种树形数据结构，其中每个父节点最多可以有两个子节点。 二叉树的每个节点（node）包含三个属性：

l data 数据

l left 左子节点的地址

l right 右子节点的地址

![06ef2148c1184b30b8b5f27538616624.png][]

满二叉树(Full Binary Tree)：每个结点要么没有子结点，要么有两个子结点

完美二叉树(Pefect Binary Tree)：每个结点都有两个子结点，所有叶子结点都在同一层

![e3867cfcb77d45eea35710b803943534.png][]

完全二叉树(Complete Binary Tree)：从根结点到倒数第二层为完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐

![310e61cb18fb48b0befed08e8003182c.png][]

二叉树天然的具有递归结构，二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的， 分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

![ec5b6fc5efef4b55ab880326419e7183.png][]

**二叉树的遍历方****式**

LeetCode 题目中，二叉树的遍历方式是最基本，也是最重要的一类题目。先介绍一下二叉树的遍历方式。

**先序遍历（前序遍历）**：按照根节点 \-> 左孩子 \-> 右孩子 的方式遍历，即「先序遍历」，每次先遍历根节点， 遍历结果为 1 2 4 5 3 6 7；

![e8fc771ddfe74f8ebd885290faf55c79.png][]

LeetCode 题目中，二叉树的遍历方式是最基本，也是最重要的一类题目。先介绍一下二叉树的遍历方式。 **中序遍历：**按照左孩子 \-> 根节点 \-> 右孩子 的方式遍历，即「中序序遍历」

遍历结果为 4 2 5 1 6 3 7；

![e9e5c4ab2ed5432eb56051192a3b6c9d.png][]

LeetCode 题目中，二叉树的遍历方式是最基本，也是最重要的一类题目。先介绍一下二叉树的遍历方式。 后序遍历：按照左孩子 \-> 右孩子 \-> 根节点 的方式遍历，即「后序序遍历」

遍历结果为 4 5 2 6 7 3 1；

![a9531930a6624805a8257666ebbd426e.png][]

LeetCode 144.二叉树的前序遍历 输出结果 \[1,2,4,5,3,6\]

![811772b646ce41558523058e968b0877.png][]

def preorderTraversal2(root):  res = list()
    if not root:
    return res
    
    stack = []  node = root
    while stack or node:
    while node:
    res.append(node.val)  stack.append(node)  node = node.left
    node = stack.pop()  node = node.right
    return res

**二叉树的遍历解题方法-** **迭代使用****栈**

LeetCode 144.二叉树的前序遍历 输出结果 \[1,2,4,5,3,6,7\]

![cc553208d6a9469a8616f0f1de41088d.png][]

**二叉树的遍历解题方****法**

LeetCode 102 中等.二叉树的层序遍历，使用队列

输出结果 \[\[1\], \[2, 3\], \[4, 5, 6, 7\]\]

![7f4aa3f3fe5c4d1a9ec9c3d994ab4aae.png][]

**二叉树的最大深度** **(LeetCode** **104)**

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。

![6656eac7a03d449998534556576815f9.png][]

如果我们知道了左子树和右子树的最大深度 l和 r，那么该二叉树的最大深度即为 max(l,r)+1

![d1845c2e81544d59a76deee75dabd438.png][]

如果我们知道了左子树和右子树的最大深度 l和 r，那么该二叉树的最大深度即为 max(l,r)+1

![42be25613c5c44cca4188b3def0170d0.png][]

def maxDepth(root):  if root is None:
    return 0
    else:
    left_height = maxDepth(root.left)  right_height = maxDepth(root.right)  return max(left_height, right_height) + 1

复杂度分析

时间复杂度：O(n) ，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。 空间复杂度：O(height) ，其中 height表示二叉树的高度。递归函数需要栈空间，而栈空 间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

**翻转二叉****树** **(LeetCode** **226)**

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

![4d4cc2573107444fa3abb95e4072942a.png][]

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

![6a08b6eea4274fa39dcfdf3c6e69b61e.png][] 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

![0affaaa41b234eb8a39db19d3e72a8c0.png][]

def invertTree(root):
    # 递归终止条件，节点为空时返回
    if not root:
    return None
    # 递归调用
    left = invertTree(root.left)  right = invertTree(root.right)
    # 将当前节点的左右子树交换 root.left, root.right = right, left  return root

**复杂度分析：**时间复杂度：O(n) 空间复杂度：O(n)

**路径总****和** **(LeetCode** **112)**

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径， 这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

![e9fc9ebe6b4e4f768e5a0fe04456c893.png][]

输入：root = \[5,4,8,11,null,13,4,7,2,null,null,null,1\], targetSum = 22

输出：true

解释：等于目标和的根节点到叶节点路径如上图所示。

使用递归的思路解决问题的时候, 需要注意递归的终止条件。

class Solution(object):
    def hasPathSum(self, root, targetSum):  """
    :type root: TreeNode
    :type targetSum: int
    :rtype: bool  """
    if not root:
    return targetSum == 0
    if self.hasPathSum(root.left, targetSum - root.val):
    return True
    if self.hasPathSum(root.right, targetSum - root.val):
    return True
    return False

使用递归的思路解决问题的时候, 需要注意递归的终止条件。下面写法中的递归终止条件考虑并不全面， 当输入为\[\], targetSum = 0 时， 下面的解法会返回True， 但实际上应该是False

**电话号码的字母组****合** **(LeetCode** **17)** **中****等**

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

![66f7905694434cabb466e713731b553e.png][]

给给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

![3878d58467854c7394ccae2a4dd57ae5.png][]

digits 是数字字符串, s(digits) 是 digits 所能代表的字母字符串

s(digits\[0…n-1\]) = letter(digits\[0\]) \+ s(digits\[1…n-1\]) = letter(digits\[0\]) \+ letter(digits\[1\]) \+ s(digits\[2…n-1\])

![158c77272c7a4fb6aacf0c2283ad46a8.png][]![f92ed44bfa0a4a4fa1ef56b8f825ea16.png][]

复杂度分析

时间复杂度：O(3n) (O(2n))

空间复杂度：*O(m+n)*

**回溯****法**

回溯法也称试探法，它的基本思想是：

l 从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，

l 当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索 直到所有的“路径”（状态）都试探过

l 这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

回溯法是暴力解法的一个主要手段

**全排****列** **(LeetCode** **46)** **中****等**

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

![51883f2a93054675a958e73b176e43db.png][]

![aa5de633772347b18868fd426c6f7688.png][]

![4fecacb13e724e6398c1839267239550.png][]

![636c76dd90e9492799bc4cf2fcd77657.png][]

def permute(nums):
    def backtrack(first=0):  if first == n:
    res.append(nums[:])
    for i in range(first, n):
    nums[first], nums[i] = nums[i], nums[first]  backtrack(first + 1)
    nums[first], nums[i] = nums[i], nums[first]  n = len(nums)
    res = []  backtrack()  return res

[_LeetCode_-_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128645069?spm=1001.2014.3001.5501
[LeetCode_--_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128644105?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128643573?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128642376?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 2]: https://blog.csdn.net/JACK_SUJAVA/article/details/128626964?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 3]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 4]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508?spm=1001.2014.3001.5501
[LeetCode_---_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560?spm=1001.2014.3001.5501
[06ef2148c1184b30b8b5f27538616624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/b32e63d251a04894bd5262a761ea196f.png
[e3867cfcb77d45eea35710b803943534.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/22624068003b444b942e506d872a17d5.png
[310e61cb18fb48b0befed08e8003182c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ef5938ef79b243699e86142201735672.png
[ec5b6fc5efef4b55ab880326419e7183.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7d1ce16415514e1da6fa1ce97f5340ec.png
[e8fc771ddfe74f8ebd885290faf55c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/508a88d3271845a7aaeca261d7125417.png
[e9e5c4ab2ed5432eb56051192a3b6c9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/4d048c25b9f7443b9103bbf43ce03f86.png
[a9531930a6624805a8257666ebbd426e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/6e8305d01f6e4f839a9e40eabf5f1031.png
[811772b646ce41558523058e968b0877.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c3839892607e4b01b1b2cc5478b22406.png
[cc553208d6a9469a8616f0f1de41088d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/d6f6f2c10eb442daad64a903544973eb.png
[7f4aa3f3fe5c4d1a9ec9c3d994ab4aae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/93789b39ef3f47c08c6f84274f01c3a2.png
[6656eac7a03d449998534556576815f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/68f96aa5f1f24429b757df1fa23f0ee5.png
[d1845c2e81544d59a76deee75dabd438.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/cda1f1d48af3442d81ff349ba0cbf230.png
[42be25613c5c44cca4188b3def0170d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/9d348d86226041749b4f8e6b5fb9db51.png
[4d4cc2573107444fa3abb95e4072942a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ff7e9e35e4474d1eace524d5affd5312.png
[6a08b6eea4274fa39dcfdf3c6e69b61e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/bf94e2efe6804cea84de8fa3fbe46d35.png
[0affaaa41b234eb8a39db19d3e72a8c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/6fba7dcd8d9043a590dd8e713e4b7cd5.png
[e9fc9ebe6b4e4f768e5a0fe04456c893.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/e50d96f612394fcb847b75f79e0a3295.png
[66f7905694434cabb466e713731b553e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/a211ea4470ed490a923fabe51da4f67a.png
[3878d58467854c7394ccae2a4dd57ae5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c4edd1f0ef9a4a6ea955890c723d03d9.png
[158c77272c7a4fb6aacf0c2283ad46a8.png]: https://img-blog.csdnimg.cn/158c77272c7a4fb6aacf0c2283ad46a8.png
[f92ed44bfa0a4a4fa1ef56b8f825ea16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3f04149aef9546cbbd9ad71529add5c3.png
[51883f2a93054675a958e73b176e43db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7094e9ca26234c5aa43c85c2db817061.png
[aa5de633772347b18868fd426c6f7688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/fb38e9b749924ec29960b06f49fb8026.png
[4fecacb13e724e6398c1839267239550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/9eb5c56aecd24e0484c45a3842fa44da.png
[636c76dd90e9492799bc4cf2fcd77657.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/60795c8546f24762aa90e615b0558628.png