代码随想录算法训练营Day-21 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树1.递归函数作用返回修剪后的二叉树的新的根节点2.终止条件遇到空节点返回NULL遇到范围之外的节点执行删除操作如果该节点值小于最小值说明右子树有可能还有符合要求的节点所以返回右子树更新后的节点如果该节点值大于最小值说明左子树有可能还有符合要求的节点所以返回左子树更新后的节点3.递归逻辑用根节点左孩子接收左子树更新后的根节点右孩子接收右子树更新后的根节点。class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(rootNULL) return NULL; if(root-vallow){ TreeNode* right trimBST(root-right,low,high); return right; } if(root-valhigh){ TreeNode* left trimBST(root-left,low,high); return left; } root-left trimBST(root-left,low,high); root-right trimBST(root-right,low,high); return root; } };108.将有序数组转换为二叉搜索树1.递归函数作用输入原数组、左边界和右边界把数组边界范围内的数据转换成二叉搜索树并返回根节点。2.终止条件当左边界大于边界时返回NULL当左边界等于右边界时返回这单个值创建的节点。3.递归逻辑先找到数组中值nums[mid]创建节点作为根节点左子树调用递归函数得到传入原数组、左边界、mid-1得到右子树也调用递归函数得到传入原数组、mid1、右边界得到。class Solution { public: TreeNode* build(vectorint nums, int left, int right){ if(left right) return NULL; if(left right){ TreeNode* root new TreeNode(nums[left]); return root; } int mid (leftright)/2; TreeNode* root new TreeNode(nums[mid]); root-left build(nums,left,mid-1); root-right build(nums,mid1,right); return root; } TreeNode* sortedArrayToBST(vectorint nums) { return build(nums,0,nums.size()-1); } };538.把二叉搜索树转换为累加树1.递归函数作用传入根节点遍历树把原值改为累加值无返回值2.终止条件遇到空节点就返回3.递归逻辑逆中序遍历右中左用一个pre来记住上一个累加值pre初始化为0中间处理步骤为把节点值prepre 节点值class Solution { public: int pre 0; void sumBST(TreeNode* root){ if(root NULL) return; sumBST(root-right); root-val pre; pre root-val; sumBST(root-left); } TreeNode* convertBST(TreeNode* root) { sumBST(root); return root; } };总结1. 二叉树的题基本上全部是递归思路学完之后最大的感悟就是遍历一定要弄明白每个题的递归三部曲递归函数作用及输入值和返回值、终止条件、单层递归逻辑把一个大问题不断拆解成子问题直到拆解到终止条件。在写递归函数的时候一定要牢记递归函数的作用一定要当做函数的功能已经实现了来写递归逻辑等函数写完了逻辑也闭环了。2. 并且要熟记遍历树的顺序前序中左右后序左右中中序左中右逆中序右中左3. 还要记住二叉搜索数的性质中序遍历元素递增还有其他特殊的类型满二叉树、完全二叉树、平衡树4. 牢记经典题从中序与后序遍历构造二叉树、二叉树的最近公共祖先5. 需要时常复习一些基础语法排序的cmp函数小顶堆、pair类型容器排序、数组切割用迭代器