将有序数组转换为二叉搜索树

这个题和之前写的 t106.从中序与后序遍历序列构造二叉树基本一致。

不一样的地方是，本题的切分点是数组nums的中间位置。然后按照以下步骤：

1. 终止条件：数组为空,return null
2. 切分点：index = left +（right-left）/ 2
3. 新建根节点：TreeNode root = new TreeNode(nums[index]);

如果数组nums只剩下一个元素，则return root

1. 分割数组：[0, index) [index + 1, len)
2. 递归左右遍历

注意【不变量】，后来[左闭右开) 和[左闭右闭]都过了，还是觉得这个题[左闭右闭]友好一些

把二叉搜索树转换为累加树

直接【右/根/左】反中序遍历一遍二叉树进行了。

1. 由于遍历整颗树，而且不用增/删BST，所以递归不需要返回类型。
2. 用一个sum 记录当前节点之前的节点和 sum
3. 右 -> 递归遍历右子树
4. 根 -> 逻辑处理
5. 左 -> 递归遍历左子树

这个题也可用迭代法，要用栈。仍然是反中序【右/根/左】

回溯

1. 组合问题

1. 对于同一集合问题：需要使用startIndex记录横向遍历的起始位置
2. 给定数组中的元素是否可以重复多次选择问题：若可重复选择，下一层递归的起始位置为 i；若不可重复选

择，下一层递归的起始位置 i

2. 组合总和（组合问题 +求和）

剪枝操作（关键）：

if(sum > target) return;

// 1. 当前累加和已经大于目标和 sum + candidates[i] <= tartget;

// 2. 先判断当前和是否大于目标和，是则不累加下一层的节点