知识库

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
}