go生物网站做蛋白定位,江苏两学一做网站,工商咨询服务,wordpress 邀请注册669.修剪二叉搜索树
这道题目需要考虑当前节点是否在[low,high]之间#xff0c; 因为是平衡二叉树#xff0c; 所以当当前节点值小于low时#xff0c;那么其左节点肯定更小#xff0c;因此删除该节点的方式是给root节点返回其右节点的递归#xff0c;注意#xff1a;这里…669.修剪二叉搜索树
这道题目需要考虑当前节点是否在[low,high]之间 因为是平衡二叉树 所以当当前节点值小于low时那么其左节点肯定更小因此删除该节点的方式是给root节点返回其右节点的递归注意这里不是直接返回右节点是因为在右子树中也有可能存在不满足条件的节点需要继续递归排查 当当前节点值大于high时那么其右节点肯定更大因此删除该节点的方式是给root节点返回其左节点的递归。 如果root.val符合在[low,high]的区间内其左右节点承接左右节点的返回值即可。 最终返回root。 代码如下
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root null) return null;else 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;}
}108.将有序数组转换为二叉搜索树
每次取中间索引的值构造节点利用递归构造平衡二叉搜索树。 要注意限定左右指针的大小条件if(right left) return null;
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) { if(nums.length 0) return null;return build(nums,0,nums.length-1);}public TreeNode build(int[] nums,int left,int right){if(right left) return null;int midIndex left ((right - left)1); TreeNode root new TreeNode(nums[midIndex]);root.left build(nums,left,midIndex-1);root.right build(nums,midIndex1,right);return root;}
}538.把二叉搜索树转换为累加树
如果是一个数组[-10,-4,4,6,7,9]要计算每个位置的累加–[12,22,26,22,16,9]可以定义一个pre记录每一次前一个数的累加然后到自身节点之后再加上自己本身的值。 那么这道题也可以在类中定义一个全局变量pre来记录每次累加的结果然后通过右中左的顺序去便利已以到使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和的目的
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int pre 0;public TreeNode convertBST(TreeNode root) {plusProcess(root);return root;}public void plusProcess(TreeNode root){//右中左遍历//终止条件if(root null) return;//右plusProcess(root.right);//中pre root.val;root.val pre;//每次改变root节点的值//左plusProcess(root.left);}
}
