day-23 代码随想录算法训练营（19）part09

669.修剪二叉搜索树

思路一：根据二叉搜索树的特性进行中间值与去区间值判断，有三种情况：1.在区间中，所以左右子树都可能在区间中； 2.在区间外面的左侧，必然只有右子树可能存在区间中；3.在区间外面的右侧，必然只有左子树可能存在区间中思路二：优化代码，不考虑在区间中的，直接考虑不在区间中的；1.当处于区间左侧，只需从右子节点开始递归查找；2.当处于区间右侧，只需从左子节点开始递归查找。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {//思路：首先考虑当前中间节点有三种情况，在low左边，在high右边if(root==nullptr) return nullptr;//中间节点在区间左边if(root->val<low){return trimBST(root->right,low,high);}//中间节点在区间右边if(root->val>high)return trimBST(root->left,low,high);//中间节点在区间内root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);return root;}
};

108.将有序数组转化位二叉搜索树

思路一：由于要高度平衡，有序数组中，每次都选择中间值作为中间节点，然后在左右分成两个区间递归去构造二叉搜索树。

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

思路：根据右中左的遍历顺序，把二叉树的节点值累加并赋值