做网站是否用数据库,商户后台管理系统,网站制作rss,wordpress快速发文章669. 修剪二叉搜索树 给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即#xff0c;如果没有被移除#xff0c;原有的父代…669. 修剪二叉搜索树 给你二叉搜索树的根节点 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]提示 树中节点数在范围 [1, 104] 内0 Node.val 104树中每个节点的值都是 唯一 的题目数据保证输入是一棵有效的二叉搜索树0 low high 104 状态自己想没写出来看了carl的思路写出来了。
思路题目的要求是把不是[low,high]区间中的其他节点都移除如果我们采取递归的方式来解决问题我们的递归终止条件肯定就是找到节点值小于low或者节点值大于high但是这时候是否只要把这个节点的左或右子节点返回就可以了呢肯定不是因为这是一个二叉搜索树如果左右子树有不符合要求的要去除掉再返回所以我们再对左或右子树进行遍历。这时可能会想如果根节点的值不符合要求怎么办呢但是我们在一开始就对节点的值进行了讨论。
class Solution {TreeNode preNodenull;public TreeNode trimBST(TreeNode root, int low, int high) {if(rootnull) return null;if(root.vallow){TreeNode righttrimBST(root.right,low,high);return right;}if(root.valhigh){TreeNode lefttrimBST(root.left,low,high);return left;}root.lefttrimBST(root.left,low,high);root.righttrimBST(root.right,low,high);return root;}
}
108. 将有序数组转换为二叉搜索树 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 平衡 二叉搜索树。 示例 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] 都是高度平衡二叉搜索树。提示 1 nums.length 104-104 nums[i] 104nums 按 严格递增 顺序排列 状态完成
思路因为要构建平衡二叉树所以左右子树节点的数量应该相差不超过1的所以每次节点都从数组的中间去取就可以了然后遍历左右数组构建左右子树完成题目要求。
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length0) return null;TreeNode nodenew TreeNode(nums[nums.length/2]);if(0nums.length/2)node.leftsortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));if(nums.lengthnums.length/2 1)node.rightsortedArrayToBST(Arrays.copyOfRange(nums,nums.length/21,nums.length));return node;}
}
538. 把二叉搜索树转换为累加树 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。 注意本题和 1038: . - 力扣LeetCode 相同 示例 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]提示 树中的节点数介于 0 和 104 之间。每个节点的值介于 -104 和 104 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。 状态完成
思路他要把二叉搜索树转换成累加树二叉搜索树是右大左小的所以采用反中序的遍历方式右中左然后累加和完成题目。
class Solution {int sum0;public TreeNode convertBST(TreeNode root) {if(rootnull) return null;convertBST(root.right);sumroot.val;root.valsum;convertBST(root.left);return root;}
}
感想今天是二叉树的最后一天感觉经过这段时间的二叉树的学习感觉学到了很多二叉树的各种遍历方式二叉树的各种属性对称、最大深度、最小深度、平衡......二叉树的修改以及构造二叉搜索树的属性二叉搜索树的属性二叉搜索树公共祖先二叉搜索树的修改和构造。继续进步
