当前位置：首页 > article >正文

二叉树习题其六【力扣】【算法学习day.13】

article 2024/10/28 20:49:20

前言

书接上篇文章二叉树习题其四，这篇文章我们将基础拓展

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.修剪二叉搜索树

题目链接:669. 修剪二叉搜索树 - 力扣（LeetCode）

题面:

基本分析:这题和删除节点思路一样

/**
 * 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 h;
    int l;
    public TreeNode trimBST(TreeNode root, int low, int high) {
         h = high;
         l = low;
        return recursion(root);
    }
    public TreeNode recursion(TreeNode root){
        if(root==null)return null;
        root.left = recursion(root.left);
        root.right = recursion(root.right);
        if(root.val>h)return root.left;
        else if(root.val<l)return root.right;
        return root;
    }
}

2.将有序数组转换成二叉搜索树

题目链接:108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

题面:

基本分析:我们每次取数组中间的值作为根节点，将这个过程递归

代码:

/**
 * 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 len;
    int[] arr;
    public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        arr = nums;
        len = n;
        return recursion(0,n-1);
    }
    public TreeNode recursion(int l,int r){
         if(l>r)return null;
         int m = (l+r)/2;
         TreeNode node = new TreeNode(arr[m]);
         node.left=recursion(l,m-1);
         node.right = recursion(m+1,r);
         return node;
    }
}

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

题目链接:538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

题面：

基本分析:就是遍历

代码:

/**
 * 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 {
    private int s = 0;

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.right); 
        s += node.val;
        node.val = s; 
        dfs(node.left); 
    }
}