Week 20 @ 2025 算法周记【二叉树 + 单调队列】

1 二叉树
2 单调队列 + 动态规划
- 2.1 LC 1696. Jump Game VI 跳跃游戏 VI

二叉树

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 (root *TreeNode)
    traverse = func (root *TreeNode) {
        if root == nil {
            return
        }

        result = append(result, root.Val)

        traverse(root.Left)
        traverse(root.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) (result int) {
    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }

        left := dfs(root.Left)
        right := dfs(root.Right)

        result = max(result, left + right)

        return max(left, right) + 1
    }

    dfs(root)
    return
}

LC 226. Invert Binary Tree 翻转二叉树

https://leetcode.com/problems/invert-binary-tree/

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

LC 116. Populating Next Right Pointers in Each Node 填充每个节点的下一个右侧节点指针

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
	q := []*Node{root}

    for {
        n := len(q)

        if q[0] == nil {
            break
        }

        for i := 0; i < n; i++ {
            q = append(q, q[i].Left, q[i].Right)
        }

        for i := 0; i < n-1; i++ {
            q[i].Next = q[i+1]
        }

        q = q[n:]
    }

    return root
}

LC 114. Flatten Binary Tree to Linked List 将二叉树展开为链表

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

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

        leftEnd := dfs(root.Left)
        rightEnd := dfs(root.Right)

        if root.Left == nil {
            if root.Right == nil {
                return root
            } else {
                return rightEnd
            }
        }
        if root.Right == nil {
            root.Right = root.Left
            root.Left = nil
            return leftEnd
        }

        leftEnd.Right = root.Right
        root.Right = root.Left
        root.Left = nil
        return rightEnd
    }

    dfs(root)
}

单调队列 + 动态规划

LC 1696. Jump Game VI 跳跃游戏 VI

https://leetcode.com/problems/jump-game-vi/description/

动态规划 (TLE)

func maxResult(nums []int, k int) int {
    n := len(nums)
    dp := make([]int, n)
    dp[n-1] = nums[n-1]

    for i := n-2; i >= 0; i-- {
        dp[i] = math.MinInt
        for j := i+1; j <= i+k && j < n; j++ {
            dp[i] = max(dp[i], nums[i] + dp[j])
        }
    }

    return dp[0]
}

动态规划 + 单调队列

func maxResult(nums []int, k int) int {
    n := len(nums)
    dp := make([]int, n)
    dp[n-1] = nums[n-1]

    q := NewMonotonicQueue()
    q.Push(dp[n-1])

    for i := n-2; i >= 0; i-- {
        dp[i] = nums[i] + q.Max()

        if q.Size() == k {
            q.Pop()
        }
        q.Push(dp[i])
    }

    return dp[0]
}

type MonotonicQueue struct {
    // 常规队列，存储所有元素
    q, maxq, minq []int
    // 元素降序排列的单调队列，头部是最大值
    // 元素升序排列的单调队列，头部是最小值
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue{
        q:    []int{},
        maxq: []int{},
        minq: []int{},
    }
}

func (mq *MonotonicQueue) Push(elem int) {
    // 维护常规队列，直接在队尾插入元素
    mq.q = append(mq.q, elem)

    // 维护 maxq，将小于 elem 的元素全部删除
    for len(mq.maxq) > 0 && mq.maxq[len(mq.maxq)-1] < elem {
        mq.maxq = mq.maxq[:len(mq.maxq)-1]
    }
    mq.maxq = append(mq.maxq, elem)

    // 维护 minq，将大于 elem 的元素全部删除
    for len(mq.minq) > 0 && mq.minq[len(mq.minq)-1] > elem {
        mq.minq = mq.minq[:len(mq.minq)-1]
    }
    mq.minq = append(mq.minq, elem)
}

func (mq *MonotonicQueue) Max() int {
    // maxq 的头部是最大元素
    return mq.maxq[0]
}

func (mq *MonotonicQueue) Min() int {
    // minq 的头部是最大元素
    return mq.minq[0]
}

func (mq *MonotonicQueue) Pop() int {
    // 从标准队列头部弹出需要删除的元素
    deleteVal := mq.q[0]
    mq.q = mq.q[1:]

    // 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
    if deleteVal == mq.maxq[0] {
        mq.maxq = mq.maxq[1:]
    }
    if deleteVal == mq.minq[0] {
        mq.minq = mq.minq[1:]
    }
    return deleteVal
}

func (mq *MonotonicQueue) Size() int {
    // 标准队列的大小即是当前队列的大小
    return len(mq.q)
}

func (mq *MonotonicQueue) IsEmpty() bool {
    return len(mq.q) == 0
}