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

力扣-数据结构-12【算法学习day.83】

article 2025/1/7 10:06:02

前言

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

习题

1.计算布尔二叉树的值

题目链接:2331. 计算布尔二叉树的值 - 力扣（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 {

    public boolean evaluateTree(TreeNode root) {
       int ans =  recursion(root);
        return ans==1?true:false;
    }
    public int recursion(TreeNode node){
        if(node.left==null&&node.right==null){
            return node.val;
        }
        int l = recursion(node.left);
        int r = recursion(node.right);
        if(node.val==2){
            return l|r;
        }else{
            return l&r;
        }
    }
}

2.出现次数最多的子树元素和

题目链接：508. 出现次数最多的子树元素和 - 力扣（LeetCode）

题面:

分析:后续遍历二叉树，并将每个子树之和存到map里，之后两次遍历map，第一次看最大值次数的key有多少个，根据此来开辟答案数组的大小，并记录最大值，然后第二次遍历将次数为最大值的数存到数组中并返回

代码:

/**
 * 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 {
    Map<Integer,Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        recursion(root);
        int count = 0;
        int max = -1;
        for (Map.Entry<Integer,Integer> entry: map.entrySet()
             ) {
                if(entry.getValue()>max){
                    max = entry.getValue();
                    count = 1;
                }
                else if(entry.getValue()==max){
                    count++;
                }
        }
        int[] ans = new int[count];
        int index = 0;
        for (Map.Entry<Integer,Integer> entry: map.entrySet()
             ) {
               if(entry.getValue()==max){
                ans[index++] = entry.getKey();
               }
        }
        return ans;

    }
    public int recursion(TreeNode node){
            if(node==null)return 0;
           int l = recursion(node.left);
           int r =  recursion(node.right);
            int flag = node.val+l+r;
            map.merge(flag,1,Integer::sum);
            return flag;
    }
}

3.二叉树的坡度

题目链接:563. 二叉树的坡度 - 力扣（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 ans = 0;
    public int findTilt(TreeNode root) {
        recursion(root);
        return ans;
    }
    public int recursion(TreeNode node){
        if(node==null)return 0;
        int l = recursion(node.left);
        int r = recursion(node.right);
        ans+=(Math.abs(l-r));
        return l+r+node.val;
    }
}

4.根据二叉树创建字符串

题目链接: 606. 根据二叉树创建字符串 - 力扣（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 {
    public String tree2str(TreeNode root) {
        String ans = recursion(root);
        return ans;
    }
    public String recursion(TreeNode node){
        if(node==null)return "";
        if(node.left==null&&node.right==null){
            return node.val+"";
        }
        String l = recursion(node.left);
        String r = recursion(node.right);
        String str = "";
            str = str+"("+l+")";
        if(!r.equals("")){
            str = str+"("+r+")";
        }
        return node.val+str;
    }
}

5.统计值等于子树平均值的节点数

题目链接: 2265. 统计值等于子树平均值的节点数 - 力扣（LeetCode）

题面:

分析:后序遍历，递归的返回值可以是一个数组，索引0用来存储当前节点以及和子节点的和，索引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 {
    int ans =0;
    public int averageOfSubtree(TreeNode root) {
        recursion(root);
        return ans;
    }
    public int[] recursion(TreeNode node){
        if(node==null){
            return new int[]{0,0};
        }
        int[] l = recursion(node.left);
        int[] r = recursion(node.right);
        int sum = node.val+l[0]+r[0];
        int count = 1+l[1]+r[1];
        if((sum/count)==node.val){
            ans++;
        }
        return new int[]{sum,count};
    }
}