• 深度优先搜索和广度优先搜索

    深度优先搜索和广度优先搜索七道习题

      在树这一块我真的很发怵，我一直在思考我如何如何地畏惧它、怕它，其实我应该思考如何记住它、使用它，所以我搜集了在LC上三个多月的每日一题，这里将针对其中的七道题进行一个归纳总结，深度优先搜索（DFS）以及广度优先搜索（BFS）。
      每道题的解法一是这两种算法中优先选用的或最容易想到的，解法二则是为了将两种算法给补足。

    1302. 层数最深叶子节点的和

    题目链接：1302. 层数最深叶子节点的和
    题目大意：计算一棵二叉树的层数最深的叶子节点的和 。
    解法（一）广度优先搜索 这是一个典型的模板，主要就是构建双端队列以及双循环。

    • q = deque([root])
    • while的大循环，用以决定是否已经走到了属的最底层；for的内循环，用来对每一层结点进行操作，并为下一层做准备。
    # 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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int: 
        
        # BFS
        q = deque([root])
        while q:
            ans = 0
           	size = len(q)
            for _ in range(size):
                node = q.popleft()
                ans += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return  ans        
        ''''''

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    解法（二）深度优先搜索 典型的递归结构，可以更好地控制树的层数。

    # 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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int: 

        # DFS
        maxLevel,ans = -1,0
        def dfs(node:Optional[TreeNode],level:int) -> None:
            if node is None:
                return
            nonlocal maxLevel,ans
            if level > maxLevel:
                maxLevel,ans = level,node.val
            elif level == maxLevel:
                ans += node.val
            dfs(node.left,level+1)
            dfs(node.right,level+1)
        dfs(root,0)
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    623. 在二叉树中增加一行

    题目链接：1302. 层数最深叶子节点的和
    题目大意：给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。注意，根节点 root 位于深度 1 。

    加法规则如下:

    • 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
    • cur 原来的左子树应该是新的左子树根的左子树；cur 原来的右子树应该是新的右子树根的右子树。
    • 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

    解法（一）深度优先搜索

    # 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 addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:

		# DFS
        if root is None: return 
        if depth == 1:
            return TreeNode(val,root,None)
        if depth == 2:
            root.left = TreeNode(val,root.left,None)
            root.right = TreeNode(val,None,root.right)
        else:
            root.left = self.addOneRow(root.left,val,depth-1)
            root.right = self.addOneRow(root.right,val,depth-1)
        return root

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    解法（二）广度优先搜索 其实不太适合，for 循环就是为了到达需要的层，有些浪费。

    # 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 addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
    
        # BFS
        if depth == 1:
            return TreeNode(val,root,None)
        cur = [root]
        for __ in range(1,depth-1):
            tmp = []
            for node in cur:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            cur = tmp
        for node in cur:
            node.left = TreeNode(val,node.left,None)
            node.right = TreeNode(val,None,node.right)
        return root

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    513. 找树左下角的值

    题目链接：513. 找树左下角的值
    题目大意：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。

    解法（一）广度优先搜索 这个比较好用，走到最后一层要最左边就OK！这里面 q.append 的顺序有必要好好想一想。

    # 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
            ans = node.val
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    解法（二）深度优先搜索 if height > curHeight时，curHeight = height 防止后续 curVal 被修改。

    # 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        curVal,curHeight = 0,0
        def dfs(node: Optional[TreeNode],height:int) -> None:
            if node is None: return 
            height += 1
            dfs(node.left,height)
            dfs(node.right,height)
            nonlocal curVal,curHeight
            if height > curHeight:
                curHeight = height
                curVal = node.val
        dfs(root,0)
        return curVal

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    1022. 从根到叶的二进制数之和

    题目链接：1022. 从根到叶的二进制数之和
    题目大意：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

    • 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
    • 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
    • 返回这些数字之和。题目数据保证答案是一个 32 位 整数。

    解法（一） 深度优先搜索

    # 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 sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode],val: int) -> int:
            if node is None: return 0
            val = (val << 1) | node.val
            if node.left is None and node.right is None: return val
            return dfs(node.left,val) + dfs(node.right,val)
        return dfs(root,0)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    解法（二）广度优先搜索 不好用啊

    # 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 sumRootToLeaf(self, root: Optional[TreeNode]) -> int:

        ans=val=0
        st = []
        pre = None
        while root or st:
            while root:
                val = (val<<1) | root.val
                st.append(root)
                root = root.left
            root = st[-1]
            if root.right is None or root.right == pre:
                if root.left is None and root.right is None:
                    ans += val
                val >>= 1
                st.pop()
                pre = root
                root = None
            else:
                root = root.right
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    310. 最小高度树

    题目链接：5310. 最小高度树
    题目大意：树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

    • 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
    • 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
    • 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

    解法（一） 广度优先搜索

    class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:

        # First, find maxlength path
        # Second, find the degree of node > 2
        if n == 1:
            return [0]
     
        g = [[] for _ in range(n)]
        deg = [0] * n
        for x,y in edges:
            g[x].append(y)
            g[y].append(x)
            deg[x] += 1
            deg[y] += 1

        q = [i for i,d in enumerate(deg) if d == 1]
        remainNodes = n
        while remainNodes > 2:
            remainNodes -= len(q)
            tmp = q
            q = []
            for x in tmp:
                for y in g[x]:
                    deg[y] -= 1
                    if deg[y] == 1:
                        q.append(y)
        return q

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    解法（二） 深度优先搜索

    class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        parents = [0] * n
        maxDepth, node = 0, -1

        def dfs(x: int, pa: int, depth: int):
            nonlocal maxDepth, node
            if depth > maxDepth:
                maxDepth, node = depth, x
            parents[x] = pa
            for y in g[x]:
                if y != pa:
                    dfs(y, x, depth + 1)
        dfs(0, -1, 1)
        maxDepth = 0
        dfs(node, -1, 1)

        path = []
        while node != -1:
            path.append(node)
            node = parents[node]
        m = len(path)
        return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    429. N 叉树的层序遍历

    题目链接：429. N 叉树的层序遍历
    题目大意：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔。

    解法（一） 广度优先搜索 好用啊

    """
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root is None: return 
        res = []
        queue = collections.deque([root])
        while queue:
            tmp = []
            size = len(queue)
            for _ in range(size):
                cur = queue.popleft()
                tmp.append(cur.val)
                for child in cur.children:
                    queue.append(child)
            res.append(tmp)
        return res

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    解法（二） 深度优先搜索

    """
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:

        res = []
        def dfs(root: 'Node',level: int) -> None:
            if root is None: return 
            if len(res) == level:
                res.append([])
            res[level].append(root.val)
            for node in root.children:
                dfs(node,level+1)
        dfs(root,0)
        return res

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    606. 根据二叉树创建字符串

    题目链接：606. 根据二叉树创建字符串
    题目大意：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

    解题（一）深度优先搜索

    # 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:

    # care for reading title, this question is for a node
    def tree2str(self, root: Optional[TreeNode]) -> str:
        ans = ""
        if root is None: return ""
        ans += str(root.val)
        if root.left:
            ans += f"({self.tree2str(root.left)})"  
        if root.right:
            if root.left is None:
                ans += '()'
            ans += f"({self.tree2str(root.right)})"
        return ans  


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    解题（二）广度优先搜索

    # 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 tree2str(self, root: Optional[TreeNode]) -> str:
        ans = ""
        st = [root]
        vis = set()
        while st:
            node = st[-1]
            if node in vis:
                if node != root:
                    ans += ')'
                st.pop()
            else:
                vis.add(node)
                if node != root:
                    ans += '('
                ans += str(node.val)
                if node.left is None and node.right:
                    ans += '()'
                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)
        return ans

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    总结

      明天要面试，这次我必须好好准备一下了，学习吧！今天凌晨记住尼采的一本书名，好长的，《查拉图斯特拉如是说》。我还看了一部分《三体：黑色森林（下部）》和《房思琪的初恋乐园》几章，说心里话看书真的可以让我放下好多没用的孤寂，无论怎么说，永远记住：我思故我在，努力地上进，努力地思考，努力地记忆，努力地努力。就这样吧，努力：奋斗！

  • 相关阅读:
    TDengineGUI无法连接TDengine
    Nacos下载与安装
    jenkins使用注意问题
    分布式与微服务的区别
    Pr 入门系列之十：基本图形
    [Acwing-Springboot] 配置Mysql
    深度剖析：数字经济下人工智能水平的新测算模型数据集
    「滑动窗口算法概述」
    STM8的C语言编程（3）+――+GPIO输出和输入
    【Kubernetes系列】Kubernetes相关概念介绍
  • 原文地址：https://blog.csdn.net/weixin_42269028/article/details/126387180