专门做商标的网站有哪些,北海市住房和城乡建设局网站,推荐网站在线看兄弟们,新中式装修效果图【LeetCode】669. 修剪二叉搜索树
题意#xff1a;给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即#xff0c;如果没有…【LeetCode】669. 修剪二叉搜索树
题意给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
思路通过递归函数的返回值这层传递给上层接收来实现删除。需要注意的是修剪时如果结点值小于左边界应该对它的右子树递归修剪如果结点值大于右边界应该对它的左子树递归修剪。
代码
/*** 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){return NULL;}if (root-val low){return trimBST(root-right, low, high);}else 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;}
};【LeetCode】108.将有序数组转换为二叉搜索树
题意给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 平衡 二叉搜索树。
思路二叉搜索树中序是升序加上需要平衡那么左右子树深度要尽可能相等。那么直接找中点作为根左子树和右子树分别递归找。
代码
/*** 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:// [l, r)TreeNode* build(vectorint nums, int l, int r){if (r l){return NULL;}int mid (l r) / 2;TreeNode *node new TreeNode(nums[mid]);node-left build(nums, l, mid);node-right build(nums, mid 1, r);return node;}TreeNode* sortedArrayToBST(vectorint nums) {if (nums.empty()){return NULL;}return build(nums, 0, nums.size());}
};【LeetCode】538.把二叉搜索树转换为累加树
题意给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
思路二叉搜索树中序递增那么累加树实际上就是每个结点的值变更为右子树的所有节点值之和加上自己的值从中序数组的角度上来看就是从后往前累加。由于中序数组是左中右方式递归所以反过来用右中左方式递归然后拿一个指针记录上一个结点的累加值即可。
代码A
/*** 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* pre NULL;void traverse(TreeNode* root){if (!root){return;}traverse(root-right);if (pre){root-val pre-val;}pre root;traverse(root-left);}TreeNode* convertBST(TreeNode* root) {if (!root){return NULL;}traverse(root);return root;}
};代码B
/*** 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* convertBST(TreeNode* root) {// 迭代法 统一遍历 右中左 通过栈变成 左中右TreeNode* pre NULL;stackTreeNode* stk;if (root){stk.push(root);}while (!stk.empty()){TreeNode* node stk.top();if (node){stk.pop();if (node-left){stk.push(node-left);}stk.push(node);stk.push(NULL);if (node-right){stk.push(node-right);}}else{stk.pop();TreeNode* now stk.top();stk.pop();if (pre){now-val pre-val;}pre now;}}return root;}
};心态“第六章 二叉树 part08” 拿下 参考资料
