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的数值加上前一个节点的数值
核心就是需要右中左顺序遍历
网友评论