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/

func openLock(deadends []string, target string) int {
    var q []string
    visited := make(map[string]bool)
    
    for _, x := range deadends {
        visited[x] = true
    } 
    
    if visited["0000"] {
        return -1
    }
    
    q = append(q, "0000")
    visited["0000"] = true
    
    step := 0
    for len(q) > 0 {
        qq := q
        q = nil
        
        for _, node := range qq {
            if node == target {
                return step
            }
                        
            for _, next := range getNext(node) {
                if visited[next] {
                    continue
                }
                
                q = append(q, next)
                visited[next] = true
            }
        }
        
        step++
    }
    
    
    return -1
}

func getNext(node string) []string {
    result := make([]string, 0, 8)
    
    nb := []byte(node)
    
    add := func(i, x int) {
        v := (int(nb[i] - '0') + x + 10) % 10
        
        nb[i] = '0' + byte(v)
    }
    
    for i := 0; i < 4; i++ {
        add(i, 1)
        result = append(result, string(nb))
        add(i, -2)
        result = append(result, string(nb))
        add(i, 1)
    }
    
    return result
}

优化：双向 BFS

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

func openLock(deadends []string, target string) int {
    visited := make(map[string]bool)
    for _, x := range deadends {
        visited[x] = true
    } 
    
    if visited["0000"] {
        return -1
    }
    
    q1 := make(map[string]bool)
    q2 := make(map[string]bool)
    
    q1["0000"] = true
    q2[target] = true
    
    step := 0
    for len(q1) > 0 && len(q2) > 0 {
        temp := make(map[string]bool)
        
        for node := range q1 {
            if q2[node] {
                return step
            }
            
            visited[node] = true
                        
            for _, next := range getNext(node) {
                if visited[next] {
                    continue
                }
                
                temp[next] = true
            }
        }
        
        step++
        q1, q2 = q2, temp
    }
    
    
    return -1
}

func getNext(node string) []string {
    result := make([]string, 0, 8)
    
    nb := []byte(node)
    
    add := func(i, x int) {
        v := (int(nb[i] - '0') + x + 10) % 10
        
        nb[i] = '0' + byte(v)
    }
    
    for i := 0; i < 4; i++ {
        add(i, 1)
        result = append(result, string(nb))
        add(i, -2)
        result = append(result, string(nb))
        add(i, 1)
    }
    
    return result
}

二叉树

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

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (result []int) {
    var traverse func(node *TreeNode)
    traverse = func(node *TreeNode) {
        if node == nil {
            return
        }
        
        result = append(result, node.Val)
        traverse(node.Left)
        traverse(node.Right)
    }
    
    traverse(root)
    return
}

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

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

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) (diameter int) {
    traverse(root, &diameter)
    return
}

func traverse(root *TreeNode, diameter *int) int {
    if root == nil {
        return 0
    }
    
    leftCount := traverse(root.Left, diameter)
    rightCount := traverse(root.Right, diameter)
    
    *diameter = max(*diameter, leftCount + rightCount + 1)
    
    return max(leftCount, rightCount) + 1
}

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

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

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

知识库

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

Analytics

BFS

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

LC 752. Open the Lock 打开转盘锁

二叉树

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

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

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

Related content