如何使用递归

func sortedArrayToBST(nums []int) *TreeNode {
    return traversal(nums,0,len(nums)-1)
}

// 定义：返回nums root 节点
func traversal(nums []int,left int , right int) *TreeNode{
    if left > right {
        return nil
    }
    mid := (left + right)/2
    root := &TreeNode{nums[mid],nil,nil}
    root.Left =  traversal(nums,left,mid-1) // 把后边 root 节点添加到当前root left 左节点上
    root.Right = traversal(nums,mid+1,right) // 把后边 root 节点添加到当前root right 左节点上
    return root
}

解决递归问题的关键在于理解问题的本质并将其分解为更小的子问题。以下是一些帮助你思考递归解题思路的步骤：

1. 识别重复模式：

   • 确定问题是否存在重复的子问题。在许多递归问题中，整个问题可以分解为与其相似但规模更小的子问题。

2. 定义递归函数：

   • 根据问题定义一个或多个递归函数，这些函数将接受问题的子集作为输入，并返回解决子问题的答案。

3. 确定基本情况：

   • 找出问题的基本情况，也就是递归终止的条件。在基本情况下，问题可以直接解决，而不需要进一步递归。

4. 分解问题：

   • 将问题分解为更小的子问题。思考如何使用子问题的解来构建原问题的解。

5. 递归工作：

   • 描述递归如何工作，包括如何从子问题的解中构建出原问题的解。

6. 合并结果：

   • 确定如何将子问题的解合并为原问题的解。

7. 编写伪代码：

   • 在编写实际代码之前，先用伪代码描述递归逻辑。

8. 考虑边界条件：

   • 考虑所有可能的边界条件，确保递归能够在所有情况下正确终止。

9. 优化性能：

   • 如果可能，考虑使用记忆化（memoization）或动态规划来避免重复计算相同的子问题。

10. 测试和调试：

    • 编写测试用例来验证递归逻辑，并调试任何出现的问题。

以排序数组转换为二叉搜索树的问题为例，解题思路可以这样形成：

• 重复模式：注意到二叉搜索树的性质，即中间的元素可以作为根，左边的元素可以作为左子树的节点，右边的元素可以作为右子树的节点。

• 定义递归函数：traversal 函数接收一个数组和两个索引，表示当前考虑的子数组。

• 确定基本情况：如果左索引大于右索引，说明子数组为空，返回 nil。

• 分解问题：选择子数组的中间元素作为当前子树的根，然后对左右两部分分别递归调用 traversal 函数。

• 递归工作：递归地构建左子树和右子树，然后将它们连接到当前根节点。

• 合并结果：通过将子树赋值给根节点的左右指针，将子问题的解合并为原问题的解。

• 编写伪代码：在脑中或纸上概述递归调用的流程。

• 考虑边界条件：确保数组索引不会超出数组边界。

• 优化性能：此问题中没有明显的性能优化空间，因为每个元素恰好使用一次。

• 测试和调试：通过在不同的数组输入上测试函数来确保其正确性。

通过这些步骤，可以构建出解决递归问题的清晰思路，并将其转化为有效的代码实现。