算法刷题笔记 (18) 字符串解码 手撕堆排序 二叉搜索树的第k大节点 二叉树的后序遍历

字符串解码

字符串解码

解题思路

利用两个栈，numStack记录需要重复的次数k，strStack记录扫描到的字符串。从左向右扫描字符串：

• 若遇到数字：压入numStack中
• 若遇到左括号或者字母：压入strStack中
• 若遇到右括号：需要字符串解码
  • strStack中的字符串依次出栈组成待重复的子串subStr，直到遇到左括号为止
  • 弹出numStack栈顶元素k，使subStr重复k次并重新压入strStack中
• 最后从底向顶扫描strStack，依次组成返回结果

解题代码

func decodeString(s string) string {
    numStack := make([]int, 0)      // 记录需要重复的次数
    strStack := make([]string, 0)   // 记录待解码的字符串
    i := 0      // 扫描字符串的下标
    for i < len(s) {
        if '0' <= s[i] && s[i] <= '9' {     // 若扫描到数字
            k := int(s[i]-'0')      // 重复次数k
            j := i+1
            for ; j < len(s) && '0' <= s[j] && s[j] <= '9'; j++ {   // 转化为int型
                k = k*10 + int(s[j]-'0')
            }
            // 重复次数入栈
            numStack = append(numStack, k)
            // 更新下标
            i = j
        } else if s[i] == ']' {     // 扫描到右括号，需要解码
            var subStr string      // 待解码的字符串
            // 依次出栈，直到遇到左括号
            cur := strStack[len(strStack)-1]
            for cur != "[" {
                subStr = cur + subStr
                strStack = strStack[:len(strStack)-1]
                cur = strStack[len(strStack)-1]
            }
            strStack = strStack[:len(strStack)-1]   // 弹出左括号
            // 弹出一个重复数字
            k := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            // 重复k次，加入到栈中
            var encoded string
            for ; k > 0; k-- {
                encoded = encoded + subStr
            }
            strStack = append(strStack, encoded)
            i++
        } else {    // 扫描到字母、左括号时直接入栈
            strStack = append(strStack, string(s[i]))
            i++
        }
    }

    var res string      // 返回结果
    // 从底向顶扫描栈，依次加入结果
    for i := 0; i < len(strStack); i++ {
        res += strStack[i]
    }

    return res
}

手撕堆排序

手撕堆排序

解题思路

堆排序过程：

• 首先建成大根堆：从最后一个分支节点开始，向上调整
• 依次将大根堆的根节点与最后一个节点交换，使大根堆的长度减一，再从新的根节点开始向下调整；直到大根堆只剩一个元素

解题代码

func sortArray(nums []int) []int {
    len := len(nums)
    heapSort(nums, len)     // 堆排序

    return nums
}

func heapSort(nums []int, len int) {
    // 建成大根堆
    buildHeap(nums, len)
    
    for len > 1 {
        // 大根堆的根节点放到最后
        nums[0], nums[len-1] = nums[len-1], nums[0]
        // 剩余节点重新调整为大根堆
        len--
        adjestHeap(nums, 0, len)
    }
    
}

func buildHeap(nums []int, len int) {
    for i := (len/2)-1; i >= 0; i-- {   // 从最后一个分支节点开始，依次向上调整堆
        adjestHeap(nums, i, len)
    }
}

func adjestHeap(nums []int, i, len int) {   // 以nums[i]为根节点调整成大根堆
    for 2*(i+1) <= len {     // 自上而下调整
        leftChild := 2*(i+1)-1      // 左孩子下标
        rightChild := leftChild+1   // 右孩子下标
        var larger int  // 左右孩子中较大者的下标
        if rightChild < len && nums[rightChild] > nums[leftChild] {
            // 右孩子较大
            larger = rightChild
        } else {
            // 左孩子较大
            larger = leftChild
        }
        if nums[i] < nums[larger] {
            // 孩子节点更大，则交换
             nums[i], nums[larger] = nums[larger], nums[i]
        }
        i = larger
    }
}

二叉搜索树的第k大节点

二叉搜索树的第k大节点

解题思路

求出右子树的节点个数rightNodeNum：

• 若k == rightNodeNum+1，当前根节点就是第k大的节点，返回根节点的值
• 若k <= rightNodeNum，说明第k大的节点在右子树中，递归寻找右子树的第k大节点
• 否则第k大的节点在左子树中，递归寻找左子树的第(k-1-rightNodeNum)大的节点

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargest(root *TreeNode, k int) int {
    rightNodeNum := nodeNum(root.Right)    // 右子树节点个数
    if k == rightNodeNum+1 {
        // 当前根节点就是第k大节点
        return root.Val
    } else if k <= rightNodeNum {
        // 第k大节点在右子树中
        return kthLargest(root.Right, k)
    } else {
        // 第k大节点在左子树中
        // 在左子树中找第(k-1-rightNodeNum)大的节点
        return kthLargest(root.Left, k-1-rightNodeNum)
    }
}

func nodeNum(root *TreeNode) int {      // 求以root为根节点的树的节点总数
    if root != nil {
        left := nodeNum(root.Left)      // 左子树的节点个数
        right := nodeNum(root.Right)    // 右子树的节点个数
        
        return 1+left+right
    } else {
        return 0
    }
}

二叉树的后序遍历

二叉树的后序遍历

解题思路

1. 递归法
2. 非递归法

解题代码

1. 递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    var postorder func(root *TreeNode)
    postorder = func(root *TreeNode) {
        if root != nil {
            postorder(root.Left)
            postorder(root.Right)
            res = append(res, root.Val)
        }
    }
    postorder(root)

    return res
}

2. 非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    cur := root
    var pre *TreeNode

    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        if len(stack) > 0 {
            cur = stack[len(stack)-1]
            if cur.Right == nil || pre == cur.Right {
                // 若栈顶节点右子树为空，或者刚刚遍历过右子树
                // 遍历栈顶节点并弹出
                res = append(res, cur.Val)
                pre = cur
                stack = stack[:len(stack)-1]
                cur = nil
            } else {
                // 否则进入右子树
                cur = cur.Right
            }
        }
    }

    return res
}