代码随想录算法训练营day23 | leetcode 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

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