Week 46 @ 2024 算法周记【BFS+二叉树】

1 BFS
- 1.1 LC 111. Minimum Depth of Binary Tree 二叉树的最小深度
- 1.2 LC 752. Open the Lock 打开转盘锁
2 二叉树

BFS

LC 111. Minimum Depth of Binary Tree 二叉树的最小深度

https://leetcode.com/problems/minimum-depth-of-binary-tree/

DFS 解法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    return dfs(root)
}

func dfs(root *TreeNode) int {
    if root.Left == nil && root.Right == nil {
        return 1
    }
    
    if root.Left == nil {
        return dfs(root.Right) + 1
    }
    if root.Right == nil {
        return dfs(root.Left) + 1
    }

    return min(dfs(root.Left), dfs(root.Right)) + 1
}

BFS 解法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    q := make([]*TreeNode, 0, 10_0000)
    
    q = append(q, root)
    depth := 1
    
    for len(q) > 0 {
        sz := len(q)
        
        for i := 0; i < sz; i++ {
            node := q[i]
            
            if node.Left == nil && node.Right == nil {
                return depth
            }
            
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        
        depth++
        q = q[sz:]
    }
    
    
    panic("impossible")
}

BFS 进一步优化空间占用
在 Go 中，如果采用 q = q[x:] 这种写法，会导致前 x 个的内存无法释放

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    var q []*TreeNode
    
    q = append(q, root)
    depth := 1
    
    for len(q) > 0 {
        sz := len(q)
        qq := q
        q = nil
        
        for i := 0; i < sz; i++ {
            node := qq[i]
            
            if node.Left == nil && node.Right == nil {
                return depth
            }
            
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        
        depth++
    }
    
    
    panic("impossible")
}

LC 752. Open the Lock 打开转盘锁

https://leetcode.com/problems/open-the-lock/

优化：双向 BFS

头尾同时遍历（实际代码上是遍历一端完再遍历另一端），出现交集时返回

二叉树

LC 144. Binary Tree Preorder Traversal 二叉树的前序遍历

https://leetcode.com/problems/binary-tree-preorder-traversal/description/

LC 543. Diameter of Binary Tree 二叉树的直径

https://leetcode.com/problems/diameter-of-binary-tree/description/

二叉树的直径定义：二叉树中任意两个节点的最大距离（边数）

LC 104. Maximum Depth of Binary Tree 二叉树的最大深度

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

深度：从根节点到叶子结点的最长节点数