BFS广度优先之二叉树的最小深度

水深无声 2023-09-30 22:20 17阅读 0赞

## 2. 二叉树的最小深度 ##

[111. 二叉树的最小深度][111.]

给定一个二叉树，找出其最小深度。
    
    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    
    说明：叶子节点是指没有子节点的节点。
    
    输入：root = [3,9,20,null,null,15,7]
    输出：2
    示例 2：
    
    输入：root = [2,null,3,null,4,null,5,null,6]
    输出：5
     
    提示：
    
    树中节点数的范围在 [0, 105] 内
    -1000 <= Node.val <= 1000

题解：

# 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 minDepth(self, root: TreeNode) -> int:
            if not root:return 0
            
            q = [root]
            step = 1
    
            while q:
                size = len(q)
                for i in range(size):
                    node = q.pop(0)
                    # 判断是否达到终点，结束条件
                    if node.left == None and node.right == None:
                        return step
    
                    # 将相邻节点添加到队列
                    if node.left != None:
                        q.append(node.left)
    
                    if node.right != None:
                        q.append(node.right)
    
                # 更新步数
                step += 1
                    
            return step
        
    
    if __name__ == '__main__':
        # root = [3,9,20,null,null,15,7]
        root = TreeNode(3)
        node1 = TreeNode(9)
        node2 = TreeNode(20)
        node3 = TreeNode(15)
        node4 = TreeNode(7)
        root.left = node1
        root.right = node2
        node2.left = node3
        node2.right = node4
        s = Solution()
        print(s.minDepth(root))

### 3. 二叉树的层序遍历 ###

[102. 二叉树的层序遍历][102.]

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
    
    示例 1：
    
    输入：root = [3,9,20,null,null,15,7]
    输出：[[3],[9,20],[15,7]]
    示例 2：
    
    输入：root = [1]
    输出：[[1]]
    示例 3：
    
    输入：root = []
    输出：[]
     
    提示：
    
    树中节点数目在范围 [0, 2000] 内
    -1000 <= Node.val <= 1000

题解：

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
            if root == None:
                return []
    
            q = [root]
            res = []
    
            while q:
                level = []  # 记录每层节点的值
                for i in range(len(q)):
                    node = q.pop()
                    level.append(node.val)
    
                    # 说明该节点没有左右节点了
                    if node.left == None and node.right == None:
                        continue
    
                    if node.left != None:
                        q.insert(0, node.left)
    
                    if node.right != None:
                        q.insert(0, node.right)
    
                # 将每层的结果添加到 res
                res.append(level)
    
            return res

[111.]: https://leetcode.cn/problems/minimum-depth-of-binary-tree/
[102.]: https://leetcode.cn/problems/binary-tree-level-order-traversal/