算法训练营Day21

发布时间:2023年12月21日

#Java #二叉树

开源学习资料

Feeling and experiences:

修剪二叉搜索树:力扣题目链接

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该?改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在?唯一的答案?。

所以结果应当返回修剪好的二叉搜索树的新的根节点。

注意,根节点可能会根据给定的边界发生改变。

/**
 * 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;
        }

        // 如果当前节点的值小于low,修剪左子树并递归右子树
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }

        // 如果当前节点的值大于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;
    }


}

1. 递归的核心:
? 针对给定的根节点,以及指定的范围?low?和?high,递归地修剪树,确保所有节点的值都在这个范围内。
2. 处理当前节点:
? 如果当前节点的值小于?low,那么它的左子树所有节点的值也一定小于?low。因此,保留修剪过的右子树。
? 如果当前节点的值大于?high,那么它的右子树所有节点的值也一定大于?high。因此,保留修剪过的左子树。
? 如果当前节点的值在?[low,?high]?范围内,递归地修剪左右子树。
3. 递归终止条件:
? 当遇到?null?节点时,递归终止。?

和昨天写的 删除二叉搜索树的节点? 比较一下:

1.?修剪二叉搜索树?(trimBST)

在修剪BST的情况下,目标是移除所有不在给定范围?[low,?high]?内的节点。关键点在于:

? 如果一个节点的值不在范围内,那么这个节点以及它的某些子树(全部或部分)需要被移除。
? 当节点的值小于?low:这意味着该节点以及它的所有左子树节点都不在范围内。因此,我们只需要关注其右子树。
? 当节点的值大于?high:这意味着该节点及其所有右子树节点都不在范围内。因此,我们只需关注其左子树。
? 在这两种情况下,我们直接?return?对应的子树,因为整个当前节点和它的某些子节点都不再有效。

2.?删除二叉搜索树中的节点

在删除BST中的特定节点的情况下,目标是移除一个特定的节点,同时保持BST的特性。这涉及到:

? 如果找到目标节点,需要根据其子节点的数量(无子节点、一个子节点、或两个子节点)来决定如何处理。
? 如果节点没有子节点,可以直接删除(返回?null)。
? 如果节点只有一个子节点,可以用其子节点替换它。
? 如果节点有两个子节点,通常需要找到右子树中最小的节点来替换删除的节点,然后删除原右子树中的那个最小节点。这种情况下不能简单地?return,因为需要保持树的结构和排序。

关键区别

? 在?修剪?的情况下,我们关注的是值是否在一个范围内,因此可能一次性移除整个子树。
? 在?删除节点?的情况下,我们只移除一个特定的节点,需要仔细处理以维持BST的属性。

将有序数组转换为二叉搜索树:力扣题目链接

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

/**
 * 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) {
    //该数组已经是升序排列的了,按照二叉搜索树的性质进行即可
    //还要保证其是一颗平衡二叉树
    return create(nums,0,nums.length - 1);

    }
    public TreeNode create(int[] nums,int left, int right){
        if(left > right){
            return null;
        }

        //选择中间的为root
        int mid = (left + right) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = create(nums,left,mid - 1);
        root.right = create(nums,mid+1,right);
        return root;
    }
}

?这道题很简单,构造一棵树写过很多次了,但是多了一个要求 :树为二叉平衡树

只要我们选择中间的数为根,那么在递归的时候,就能尽可能保证平衡左右子树的高度。

把二叉搜索树转换为累加树:力扣题目链接

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 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 {
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return root;
        }
        //利用逆中序的方法
        Stack<TreeNode> stack = new Stack<TreeNode>();
        dfs(root, stack);
        TreeNode node = stack.pop();
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            cur.val += node.val;
            node = cur;
        }
        return root;
    }
    private void dfs(TreeNode root, Stack<TreeNode> stack) {
        if(root != null) {
            dfs(root.left, stack);
            stack.push(root);
            dfs(root.right, stack);
        }
    }
}

?

1. 中序遍历的逆序:
? 由于BST的性质,进行标准的中序遍历(左-根-右)会得到一个升序的节点序列。但在这个问题中,我们需要逆序进行中序遍历(右-根-左),这样可以从最大的节点开始遍历到最小的节点。

2. 使用栈进行遍历:
? 栈用于存储遍历过程中的节点。这个栈帮助我们按照逆中序的方式遍历树,即首先访问右子树,然后是根节点,最后是左子树。

3. 节点值的更新:
? 在遍历过程中,每个节点的值更新为它自己的值加上所有之前遍历过的节点的值。这保证了每个节点的新值等于其原始值加上所有大于它的节点的值。

4. 递归方法:
? 使用递归方法?f?进行逆中序遍历,并将节点按顺序推入栈中。

5. 累加和的维护:
? 通过在栈中逐个弹出节点并更新它们的值,维护一个累加和。每个节点的新值就是它的原始值加上这个累加和。

?

?以下是递归遍历:

/**
 * 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 sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

该题目,主要就是用到的中序的逆序,读懂题目就简单了!

盛气光引炉烟,

素草寒生玉佩。

Fighting!
?

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