代码随想录算法训练营第二十三天|669. 修剪二叉搜索树、108

669. 修剪二叉搜索树 

递归三部曲：

确定递归函数的参数以及返回值

确定终止条件

遇到空节点返回

确定单层递归的逻辑

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点

如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

修剪过程比较巧妙

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

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

递归三部曲：

确定递归函数返回值及其参数

传入数组，左下标left和右下标right

确定递归终止条件

当区间 left > right的时候，就是空节点了

确定单层递归的逻辑

首先取数组中间元素的位置

取了中间位置，就开始以中间位置的元素构造节点，代码：TreeNode* root = new TreeNode(nums[mid]);。

接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。

最后返回root节点

int mid = left + ((right - left) / 2);

TreeNode* root = new TreeNode(nums[mid]);

root->left = traversal(nums, left, mid - 1);

root->right = traversal(nums, mid + 1, right);

return root;

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

递归函数参数以及返回值

这里很明确了，不需要递归函数的返回值做什么操作了，要遍历整棵树。

同时需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了。

确定终止条件

遇空就终止。

确定单层递归的逻辑

注意要右中左来遍历二叉树， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值

核心就是需要右中左顺序遍历