网站建设的难点,国外做糖网站,网站改版注意事项,天津网站搜索优化1. 修剪二叉搜索树
669. 修剪二叉搜索树https://leetcode.cn/problems/trim-a-binary-search-tree/
给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留…1. 修剪二叉搜索树
669. 修剪二叉搜索树https://leetcode.cn/problems/trim-a-binary-search-tree/
给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
示例 1 输入root [1,0,2], low 1, high 2
输出[1,null,2]
示例 2 输入root [3,0,4,null,2,null,null,1], low 1, high 3
输出[3,2,null,1]
解题思路
只需要删除大于high的和小于low的
出于二叉树的特性可以进行递归操作
终止条件root为null的时候返回null参数和返回值root和high和low返回递归处理后的子树的头节点递归逻辑对于当前的root节点有两种情况一种是小于low的那么左子树都不能要所以直接递归处理右节点返回一种是大于high的右子树都不能要递归处理左节点返回如果root满足那就递归处理左右节点然后返回root
代码
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root null)return root;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;}
}
2. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1 输入nums [-10,-3,0,5,9]
输出[0,-3,9,-10,null,5]
解释[0,-10,5,null,-3,null,9] 也将被视为正确答案 示例 2 输入nums [1,3]
输出[3,1]
解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
解题思路
要构建一个高度平衡的二叉平衡树可以找到一个中间值作为根节点然后递归左右区间作为子树
代码
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return BST(nums, 0, nums.length);}private TreeNode BST(int[] nums, int start, int end) {if (start end)return null;if (start 1 end)return new TreeNode(nums[start]);int mid start (end - start) / 2;TreeNode root new TreeNode(nums[mid]);root.left BST(nums, start, mid);root.right BST(nums, mid 1, end);return root;}
}
3. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
示例 1 输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2
输入root [0,null,1]
输出[1,null,1]
示例 3
输入root [1,0,2]
输出[3,3,2]
示例 4
输入root [3,2,4,1]
输出[7,9,4,10] 解题思路
只需要对整个节点的node进行逆序遍历也就是右中左然后使用一个全局变量记录累积值。
代码
class Solution {int num 0;public TreeNode convertBST(TreeNode root) {if (root null)return null;convertBST(root.right);root.val num;num root.val;convertBST(root.left);return root;}
}
