递归思维.md

递归思维

例子

344. 反转字符串

func reverseString(s []byte) {
    res := make([]byte, 0)
    reverse(s, 0, &res)
    for i := 0; i < len(s); i++ {
        s[i] = res[i]
    }
}

func reverse(s []byte, i int, res *[]byte) {
    if i == len(s) {
        return
    }
    reverse(s, i + 1, res)
    * res = append(*res, s[i])
}

func reverseString(s []byte) {
    n := len(s)
    for i := 0; i < n / 2; i++ {
        s[i], s[n-i-1] = s[n-i-1], s[i]
    }
}

24. 两两交换链表中的节点

func swapPairs(head *ListNode) *ListNode {
    return helper(head)
}

func helper(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    nextHead := head.Next.Next
    next := head.Next
    next.Next = head
    head.Next = helper(nextHead)
    return next
}

95. 不同的二叉搜索树 II

func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return nil
    }
    return generate(1, n)
}

func generate(start, end int) []*TreeNode {
    if start > end {
        return []*TreeNode{nil}
    }
    ans := make([]*TreeNode, 0)

    for i := start; i <= end; i++ {
        lefts := generate(start, i - 1)
        rights := generate(i + 1, end)

        for j := 0; j < len(lefts); j++ {
            for k := 0; k < len(rights); k++ {
                root := &TreeNode{Val: i}
                root.Left = lefts[j]
                root.Right = rights[k]
                ans = append(ans, root)
            }
        }
    }
    return ans
}