LeetCode 669. 修剪二叉搜索树
分析1.0
递归遍历树时删除符合条件(不在区间中)的节点-如何遍历如何删除
如果当前节点大于范围,递归左树,反之右树
当前节点不在范围内,删除它,把它的子树返回给上一层
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;
}
}
失误 不是删除在区间的节点,而是删除不在区间中的节点
LeetCode 108.将有序数组转换为二叉搜索树
分析1.0
二叉搜索树的中序遍历是递增序列,要将升序数组转换成一颗高度平衡的二叉搜索树
- 找到树根-递归找树根
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sort(nums, 0, nums.length - 1);
}
public TreeNode sort(int[] nums, int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start)/2;
TreeNode root = new TreeNode(nums[mid]);
//System.out.println(nums[mid]);
//System.out.println("start "+start+"end"+end);
root.left = sort(nums, start, mid-1);
root.right = sort(nums, mid+1, end);
return root;
}
}
失误
递归结束条件不能是 left == right,想法很好,但是可能存在right直接比left小的情况,这样永远返回不了
LeetCode 538.把二叉搜索树转换为累加树
分析1.0
乍一看没有看懂题目,看看示例搞明白惹
二叉搜索树中序序列是递增的,换成数组就是从后往前累加 到某处再将结果置换成新值
应从最大的值加起,也就是右中左,但是涉及到一个值累积的问题,便可以通过外部计数器的方式实现
class Solution {
int num = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
convertBST(root.right);
num += root.val;
root.val = num;
convertBST(root.left);
return root;
}
}
分析2.0
其实这里就是要知道当前节点的上一个节点 用pre就好
总结
- 判断结束条件 ==要慎用,可能出现不了==的情况
- 遍历树可以引入sum 对节点值进行处理或者暂存,以便下一步遍历时能够访问,替代了返回节点的功能
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
标签:right,return,随想录,二叉,start,搜索,TreeNode,root From: https://www.cnblogs.com/cupxu/p/17129105.html