算法训练营Day23(二叉树）

2023-12-21 13:35:27

?669.?修剪二叉搜索树?

669. 修剪二叉搜索树 - 力扣（LeetCode）

这里本身不难，更多的是递归的技巧，在脑子里模拟一遍递归逻辑，记忆好模板就好了。

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.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }
}

?108.将有序数组转换为二叉搜索树??

注意一下区间的定义就好了，很简单的题

正常的构造就行，因为数组本身就是有序的，找中点去构造，即符合二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return travel(nums,0,nums.length-1);
    }
    private TreeNode travel(int [] nums,int left,int right){
        if(left>right) return null;
        int mid = (left+right)>>1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = travel(nums,left,mid-1);
        root.right = travel(nums,mid+1,right);
        return root;
    }
}

?538.把二叉搜索树转换为累加树??

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

记住二叉树中双指针，以及右中左的遍历顺序，就好了，soEasy;

class Solution {
    private TreeNode pre= null;
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return null;
        convertBST(root.right);
        if(pre!=null){
            root.val = root.val+pre.val;
        }
        pre = root;
        convertBST(root.left);
        return root;
    }
}

总结

我的总结就是一般二叉树用后序，来做到孩子节点信息穿给根节点

二叉搜索树用中序，利用自增特效

求深度这些用前序

但是：涉及一些构造，比如二叉搜索树，或者一些不用管遍历顺序的题目，就淡化一下遍历顺序的思想，以免只顾着遍历顺序而影响我们做题的思考

卡哥的总结：

代码随想录 (programmercarl.com)

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135125186
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。