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

一、高频题

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-颜色填充