网站 宣传方案,做微信小程序是不是不用做网站,网站备案 子域名,如何建设网站教育目录
669. 修剪二叉搜索树
前言
思路
递归法
108.将有序数组转换为二叉搜索树
前言
递归法
538.把二叉搜索树转换为累加树
前言
递归法
总结 669. 修剪二叉搜索树 题目链接 文章链接 前言 本题承接昨天二叉搜索树的插入和删除操作题目#xff0c;要对整棵二叉搜索树…目录
669. 修剪二叉搜索树
前言
思路
递归法
108.将有序数组转换为二叉搜索树
前言
递归法
538.把二叉搜索树转换为累加树
前言
递归法
总结 669. 修剪二叉搜索树 题目链接 文章链接 前言 本题承接昨天二叉搜索树的插入和删除操作题目要对整棵二叉搜索树进行遍历修剪。
思路 因为要遍历整棵二叉搜索树因此不需要返回值也可以我们可以完成修剪的操作但是有返回值更方便可以通过递归函数的返回值来移除节点。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root NULL) return NULL;if (root-val low){//寻找右子树符合区间的节点TreeNode* right trimBST(root-right, low, high);return right;}if (root-val high){//寻找左子树符合区间的节点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.将有序数组转换为二叉搜索树 题目链接 文章链接 前言 题目强调得到的二叉搜索树必须平衡因此不可以采用简单的线性结构构造二叉搜索树。要将有序数组的中值作为根节点左侧作为左子树右侧作为右子树。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:TreeNode* traversal(vectorint nums, int left, int right){if (left right) return NULL;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;}
public:TreeNode* sortedArrayToBST(vectorint nums) {TreeNode* root traversal(nums, 0, nums.size() - 1);return root;}
}; 在确定数组中值的时候以及递归时左右边界的确定要严格根据遵守二分法本题算法采用左闭右闭的区间形式。
538.把二叉搜索树转换为累加树 题目链接 文章链接 前言 将二叉搜索树转化为累加树本质上和数组逆序累加求和的思路一致难点在于二叉树的遍历顺序。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int pre 0; //记录前一个节点的数值void traversal(TreeNode* cur){if (cur NULL) return;traversal(cur-right);cur-val pre;pre cur-val;traversal(cur-left);}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
}; 本题单层递归采用右中左的逆中序遍历顺序。
总结 二叉树正式完结后期要多回顾总结。
