算法刷题笔记 (25) 对角线遍历 长度最小的子数组 删除二叉搜索树中的节点

对角线遍历

对角线遍历

解题思路

划分为两种遍历形式：朝着右上方遍历和朝着左下方遍历。

解题代码

func findDiagonalOrder(mat [][]int) []int {
    m := len(mat)
    n := len(mat[0])
    res := make([]int, m*n)     // 记录遍历序列
    count := 0  // 记录已经遍历的元素个数
    row, col := 0, 0    // 待遍历元素所在行、列
    for count < m*n {
        if row == m-1 && col == n-1 {
            // 遍历到最后一个元素（右下角的元素）
            res [count] = mat[row][col]
            break
        }
        // 向斜右上方遍历
        for row >= 0 && col < n {
            res[count] = mat[row][col]
            count++
            row--
            col++
        }
        if col < n {
            // 在遍历矩阵的左上部分
            row++
        } else {
            // 在遍历矩阵的右下部分
            row += 2
            col--
        }
        // 向斜左下方遍历
        for row < m && col >= 0 {
            res[count] = mat[row][col]
            count++
            row++
            col--
        }
        if row < m {
            // 在遍历矩阵的左上部分
            col++
        } else {
            // 在遍历矩阵的右下部分
            col += 2
            row--
        }
    }

    return res
}

长度最小的子数组

长度最小的子数组

解题思路

利用滑动窗口的思想，start指向窗口的起始位置，end指向窗口的终止位置的后一位，sum为窗口内数字之和：

• 如果sum < target，end需要向后移动
• 如果sum > target，start需要向前移动

解题代码

func minSubArrayLen(target int, nums []int) int {
    start, end := 0, 0  // 滑动窗口的起始位置、终止位置的后一位
    minLen := math.MaxInt64     // 连续子数组的最小长度
    sum := 0
    for end < len(nums) {
        // end向后移动
        for sum < target && end < len(nums) {
            sum += nums[end]
            end++    
        }
        // start向前移动
        for sum >= target {
            if end-start < minLen {
                minLen = end-start
            }
            sum -= nums[start]
            start++
        }
    }

    if minLen == math.MaxInt64 {
        // 不存在符合条件的子数组
        return 0
    } else {
        // 存在
        return minLen
    }
}

删除二叉搜索树中的节点

删除二叉搜索树中的节点

解题思路

• 当待删除节点是叶子节点时，直接删除

• 待删除节点只有一个分支时，用其分支节点代替待删除的节点

• 待删除节点的左右子树均存在时：

  • 找到其后继节点，交换后继节点和当前待删除节点的值
  • 删除右子树中值为key的节点

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root != nil {
        if root.Val == key {
            // 找到待删除节点
            if root.Left == nil && root.Right == nil {
                // 叶子节点直接删除
                return nil
            }
            if root.Left != nil && root.Right == nil {
                // 只有左子树，用左子树代替
                return root.Left
            }
            if root.Right != nil && root.Left == nil {
                // 只有右子树，用右子树代替
                return root.Right
            }
            // 左右子树都存在
            // 找到后继节点
            next := nextNode(root)
            // 交换后继节点与当前节点的值
            root.Val, next.Val = next.Val, root.Val
            // 在右子树中删除值为key的节点
            root.Right = deleteNode(root.Right, key)
        } else if root.Val > key {
            // 进入左子树查找
            root.Left =  deleteNode(root.Left, key)
        } else {
            // 进入右子树查找
            root.Right = deleteNode(root.Right, key)
        }
    }

    return root
}

// 返回以root为根节点，中序遍历中的后继节点
func nextNode(root *TreeNode) *TreeNode {
    // 后继节点为root右子树的最左边的节点
    next := root.Right
    for next.Left != nil {
        next = next.Left
    }
    return next
}