wordpress禁用灯箱效果,广州seo网站管理,网址查询地址查询站长之家,短视频平台推广方案669. 修剪二叉搜索树
题目
参考文章 思路#xff1a;这题其实就是删除不符合上下边界的节点。注意#xff1a;这里删除不符合上下边界节点时#xff0c;这个不符合上下边界的节点的左或右子树可能存在符合上下边界的节点#xff0c;所i有每次比较完之后#xff0c;要继…669. 修剪二叉搜索树
题目
参考文章 思路这题其实就是删除不符合上下边界的节点。注意这里删除不符合上下边界节点时这个不符合上下边界的节点的左或右子树可能存在符合上下边界的节点所i有每次比较完之后要继续遍历其左或右子树直到把所有不符合上下边界的节点都删除为止 代码
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root null) {return null;}if (root.val low) {return trimBST(root.right, low, high); //当当前节点值小于下边界时就直接继续遍历当前节点的右子树即可找到符合上下边界的值}if (root.val high) {//当当前节点值大于上边界时就直接继续遍历当前节点的左子树即可找到符合上下边界的值return trimBST(root.left, low, high);}// root在[low,high]范围内//接入如何条件的左右孩子root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);return root;}
}
108.将有序数组转换为二叉搜索树
题目
参考文章 思路这道题目是构造平衡二叉搜索树所以我们构造的时候不能只在节点的某一边构造。因此我们要从数组的中间位置开始构造根节点我们采用左闭右开的方式。因为是左闭右开所以非法条件为 leftright然后每次取中间数组位置构建值构建完后又继续构建左右节点 代码
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}public TreeNode sortedArrayToBST(int[] nums, int left, int right) {if (left right) {return null;}if (right - left 1) {//当遍历到当前数组的的下标位置相差1时表示已经在数组边界所以直接构建节点返回即可return new TreeNode(nums[left]);}int mid left (right - left) / 2;TreeNode root new TreeNode(nums[mid]);root.left sortedArrayToBST(nums, left, mid);root.right sortedArrayToBST(nums, mid 1, right);return root;}
}
538.把二叉搜索树转换为累加树
题目
参考文章 思路这题目的意思就是让我们从这个二叉搜索树从大到小遍历原来左中右的情况是从小到大遍历所以从大到小遍历就是右中左。了解这个这题目就很好解决了。这里设置一个int sum用于存储累加值而且每次累加后当前记得的值就更新为sum题目要求按右中左去遍历即可 代码
class Solution {int sum;public TreeNode convertBST(TreeNode root) {sum 0;convertBST1(root);return root;}// 按右中左顺序遍历累加即可public void convertBST1(TreeNode root) {if (root null) {return;}convertBST1(root.right);sum root.val;root.val sum;convertBST1(root.left);}
} 二叉树总结
在二叉树题目选择什么遍历顺序是不少同学头疼的事情我们做了这么多二叉树的题目了Carl给大家大体分分类。 涉及到二叉树的构造无论普通二叉树还是二叉搜索树一定前序都是先构造中节点。 求普通二叉树的属性一般是后序一般要通过递归函数的返回值做计算。 求二叉搜索树的属性一定是中序了要不白瞎了有序性了。
注意在普通二叉树的属性中我用的是一般为后序例如单纯求深度就用前序二叉树找所有路径 (opens new window)也用了前序这是为了方便让父节点指向子节点。
所以求普通二叉树的属性还是要具体问题具体分析。
