LeetCode-题目详解：深度优先搜索、广度优先遍历

我不是女神ヾ 2023-10-04 14:39 14阅读 0赞

## 一、高频题 ##

### 1、高频题 ###

#### 1.1、105-从前序与中序遍历序列构造二叉树 ####

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

--------------------

方法一：递归【O(n)，其中 n 是树中的节点个数】

class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
                if preorder_left > preorder_right:
                    return None
                
                # 前序遍历中的第一个节点就是根节点
                preorder_root = preorder_left
                # 在中序遍历中定位根节点
                inorder_root = index[preorder[preorder_root]]
                
                # 先把根节点建立出来
                root = TreeNode(preorder[preorder_root])
                # 得到左子树中的节点数目
                size_left_subtree = inorder_root - inorder_left
                # 递归地构造左子树，并连接到根节点
                # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
                root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
                # 递归地构造右子树，并连接到根节点
                # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
                root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
                return root
            
            n = len(preorder)
            # 构造哈希映射，帮助我们快速定位根节点
            index = {
        element: i for i, element in enumerate(inorder)}
            return myBuildTree(0, n - 1, 0, n - 1)

方法二：递归

1.规律

前序：（root.val）\[左子树的结点的数值们，长度为left\_len\] \[右子树的结点的数值们，长度为right\_len\]

中序：\[左子树的结点的数值们，长度为left\_len\] （root.val）\[右子树的结点的数值们，长度为right\_len\]

idx = inorder.index(root.val) 就是左子树的结点个数

2.切片比较好用。用指针容易思维搞乱，且边界不好维护

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            # 递归结束条件
            if not preorder:
                return None
            root_val = preorder[0]
            root_idx = inorder.index(root_val)
            root = TreeNode(root_val)
    
            # 前序遍历中，索引root_idx前的节点为根+左子树，preorder[1: root_idx + 1]为左子树数组
            # 中序遍历中，索引root_idx为根节点，inorder[0: root_idx]为左子树数组
            root.left = self.buildTree(preorder[1:root_idx + 1], inorder[0:root_idx])
    
            # 索引root_idx后的节点为右子树所有节点，preorder[root_idx + 1:]为右子树数组
            # 中序遍历中，索引root_idx为根节点，inorder[root_idx + 1: ]为右子树数组
            root.right = self.buildTree(preorder[root_idx + 1:], inorder[root_idx + 1:])
            return root

方法三：迭代【O(n)，其中 n 是树中的节点个数】

class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            if not preorder:
                return None
    
            root = TreeNode(preorder[0])
            stack = [root]
            inorderIndex = 0
            for i in range(1, len(preorder)):
                preorderVal = preorder[i]
                node = stack[-1]
                if node.val != inorder[inorderIndex]:
                    node.left = TreeNode(preorderVal)
                    stack.append(node.left)
                else:
                    while stack and stack[-1].val == inorder[inorderIndex]:
                        node = stack.pop()
                        inorderIndex += 1
                    node.right = TreeNode(preorderVal)
                    stack.append(node.right)
    
            return root
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#### 1.2、131-分割回文串 ####

#### 1.3、200-岛屿数量 ####

#### 1.4、124-二叉树中的最大路径和 ####

#### 1.5、394-字符串解码 ####

#### 1.6、199-二叉树的右视图 ####

#### 1.7、17-电话号码的字母组合 ####

#### 1.8、104-二叉树的最大深度 ####

#### 1.9、101-对称二叉树 ####

#### 1.10、679-24 点游戏 ####

#### 1.11、98-验证二叉搜索树 ####

#### 1.12、721-账户合并 ####

#### 1.13、257-二叉树的所有路径 ####

#### 1.14、剑指 Offer 34-二叉树中和为某一值的路径 ####

#### 1.15、547-省份数量 ####

### 2、中频题 ###

#### 2.1、494-目标和 ####

#### 2.2、113-路径总和 II ####

#### 2.3、剑指 Offer 55 - I-二叉树的深度 ####

#### 2.4、110-平衡二叉树 ####

#### 2.5、695-岛屿的最大面积 ####

#### 2.6、130-被围绕的区域 ####

#### 2.7、207-课程表 ####

#### 2.8、106-从中序与后序遍历序列构造二叉树 ####

#### 2.9、1631-最小体力消耗路径 ####

#### 2.10、108-将有序数组转换为二叉搜索树 ####

#### 2.11、112-路径总和 ####

#### 2.12、100-相同的树 ####

#### 2.13、129-求根节点到叶节点数字之和 ####

#### 2.14、面试题 16.19-水域大小 ####

#### 2.15、剑指 Offer 12-矩阵中的路径 ####

#### 2.16、99-恢复二叉搜索树 ####

#### 2.17、337-打家劫舍 III ####

#### 2.18、329-矩阵中的最长递增路径 ####

#### 2.19、剑指 Offer 55 - II-平衡二叉树 ####

#### 2.20、114-二叉树展开为链表 ####

#### 2.21、417-太平洋大西洋水流问题 ####

#### 2.22、面试题 04.05-合法二叉搜索树 ####

#### 2.23、514-自由之路 ####

#### 2.24、1319-连通网络的操作次数 ####

#### 2.25、111-二叉树的最小深度 ####

#### 2.26、301-删除无效的括号 ####

#### 2.27、491-递增子序列 ####

#### 2.28、959-由斜杠划分区域 ####

#### 2.29、面试题 04.02-最小高度树 ####

#### 2.30、934-最短的桥 ####

#### 2.31、210-课程表 II ####

#### 2.32、1203-项目管理 ####

#### 2.33、332-重新安排行程 ####

#### 2.34、面试题 17.22-单词转换 ####

#### 2.35、987-二叉树的垂序遍历 ####

#### 2.36、109-有序链表转换二叉搜索树 ####

#### 2.37、116-填充每个节点的下一个右侧节点指针 ####

#### 2.38、947-移除最多的同行或同列石头 ####

#### 2.39、743-网络延迟时间 ####

#### 2.40、515-在每个树行中找最大值 ####

#### 2.41、538-把二叉搜索树转换为累加树 ####

#### 2.42、685-冗余连接 II ####

#### 2.43、839-相似字符串组 ####

#### 2.44、785-判断二分图 ####

#### 2.45、783-二叉搜索树节点最小距离 ####

#### 2.46、1489-找到最小生成树里的关键边和伪关键边 ####

#### 2.47、968-监控二叉树 ####

#### 2.48、1145-二叉树着色游戏 ####

#### 2.49、面试题 17.07-婴儿名字 ####

#### 2.50、778-水位上升的泳池中游泳 ####

#### 2.51、863-二叉树中所有距离为 K 的结点 ####

#### 2.52、563-二叉树的坡度 ####

#### 2.53、面试题 04.04-检查平衡性 ####

#### 2.54、690-员工的重要性 ####

#### 2.55、430-扁平化多级双向链表 ####

#### 2.56、827-最大人工岛 ####

#### 2.57、897-递增顺序搜索树 ####

#### 2.58、1530-好叶子节点对的数量 ####

#### 2.59、1559-二维网格图中探测环 ####

#### 2.60、559-N 叉树的最大深度 ####

#### 2.61、872-叶子相似的树 ####

#### 2.62、529-扫雷游戏 ####

#### 2.63、851-喧闹和富有 ####

#### 2.64、面试题 04.12-求和路径 ####

#### 2.65、473-火柴拼正方形 ####

#### 2.66、546-移除盒子 ####

#### 2.67、323-无向图中连通分量的数目 ####

#### 2.68、1466-重新规划路线 ####

#### 2.69、542-01 矩阵 ####

### 3、低频题 ###

#### 3.1、938-二叉搜索树的范围和 ####

#### 3.2、753-破解保险箱 ####

#### 3.3、834-树中距离之和 ####

#### 3.4、1810-Minimum Path Cost in a Hidden Grid ####

#### 3.5、366-寻找二叉树的叶子节点 ####

#### 3.6、749-隔离病毒 ####

#### 3.7、971-翻转二叉树以匹配先序遍历 ####

#### 3.8、133-克隆图 ####

#### 3.9、211-添加与搜索单词 - 数据结构设计 ####

#### 3.10、638-大礼包 ####

#### 3.11、1302-层数最深叶子节点的和 ####

#### 3.12、576-出界的路径数 ####

#### 3.13、733-图像渲染 ####

#### 3.14、797-所有可能的路径 ####

#### 3.15、117-填充每个节点的下一个右侧节点指针 II ####

#### 3.16、489-扫地机器人 ####

#### 3.17、513-找树左下角的值 ####

#### 3.18、1306-跳跃游戏 III ####

#### 3.19、1740-找到二叉树中的距离 ####

#### 3.20、1059-从始点到终点的所有路径 ####

#### 3.21、1766-互质树 ####

#### 3.22、1391-检查网格中是否存在有效路径 ####

#### 3.23、488-祖玛游戏 ####

#### 3.24、490-迷宫 ####

#### 3.25、694-不同岛屿的数量 ####

#### 3.26、924-尽量减少恶意软件的传播 ####

#### 3.27、1443-收集树上所有苹果的最少时间 ####

#### 3.28、261-以图判树 ####

#### 3.29、664-奇怪的打印机 ####

#### 3.30、865-具有所有最深节点的最小子树 ####

#### 3.31、1376-通知所有员工所需的时间 ####

#### 3.32、1457-二叉树中的伪回文路径 ####

#### 3.33、526-优美的排列 ####

#### 3.34、802-找到最终的安全状态 ####

#### 3.35、1020-飞地的数量 ####

#### 3.36、1448-统计二叉树中好节点的数目 ####

#### 3.37、886-可能的二分法 ####

#### 3.38、1038-把二叉搜索树转换为累加树 ####

#### 3.39、1254-统计封闭岛屿的数目 ####

#### 3.40、面试题 08.10-颜色填充 ####

LeetCode-题目详解：深度优先搜索、广度优先遍历

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-题目详解：深度优先搜索、广度优先遍历

相关【图】概念、存储结构、广度优先遍历遍历、深度优先遍历 - 详解

相关深度优先搜索广度优先搜索

相关漫画：深度优先遍历和广度优先遍历

相关图：深度优先遍历&广度优先遍历

相关深度优先遍历与广度优先遍历（二）

相关深度优先遍历与广度优先遍历（一）

相关图的遍历之深度优先搜索和广度优先搜索

相关图的遍历——深度优先搜索+广度优先搜索

相关图的遍历（广度优先遍历、深度优先遍历）