LeetCode刷题31-40

LeetCode刷题
Word count: 3.1k   |   Reading time≈ 13 min

①222.完全二叉树的节点个数

题目：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

普遍使用法，未利用完全二叉树的特点

1
2
3
4
5
6
public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

思考：完全二叉树的特点
如果左右子树的深度相同 left == right 那么左子树一定是满的，右子树不一定
如果左右子树的深度不同 left != right 那么右子树一定满的，right == left-1

完全二叉树深度的特点：height = left + 1 (整颗树的深度 = 左子树的深度 + 根结点1)

满二叉树深度为 h ，则其结点数为：2^h -1
1 << h 可表示 2 的 h 次方

利用完全二叉树的特点(求深度未用递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = countHeight(root.left);
        int right = countHeight(root.right);

        if(left == right){
            return countNodes(root.right) + (1 << left);
        }else{
            return (1 << right) + countNodes(root.left);
        }
    }
    //求深度
    public int countHeight(TreeNode root){
        int height = 0;
        while(root != null){
            height ++;
            root = root.left;
        }
        return height;
    }
}

②226.翻转二叉树

题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例图

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        //分别翻转root的左子树和右子树
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        //将root的左子树指针指向right，将右子树指针指向left，完成翻转
        root.left = right;
        root.right = left;
        return root;
    }

③257.二叉树的所有路径

题目：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

当前结点如果不为 null
将结点加入到 拼接器中
判断当前结点是记否为叶子结点
是：将拼接器中当前路径加入到 paths 中
否：添加 -> 、 递归

深度优先搜索、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths =  new ArrayList<String>();
        getPaths(root,"",paths);
        return paths;
    }

    public void getPaths(TreeNode root,String path,List<String> paths){
        if(root != null){
            StringBuilder sb = new StringBuilder(path);
            sb.append(Integer.toString(root.val));
            if(root.left == null && root.right == null){
                //是叶子结点
                paths.add(sb.toString());
            }else{
                //不是叶子结点
                sb.append("->"); //拼接->
                //继续递归
                getPaths(root.left,sb.toString(),paths);
                getPaths(root.right,sb.toString(),paths);
            }
        }
    }
}

④404.左叶子之和

题目：给定二叉树的根节点 root ，返回所有左叶子之和。

思考：是叶子 且是左叶子
树不为空的情况下，分别判断左子树和右子树

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        //要判空
        return root != null ? getSum(root) : 0;
    }

    public int getSum(TreeNode root){
        int sum = 0;
        //有左孩子
        if(root.left != null){
            //如果是叶子sum加其值
            //如果不是叶子就继续递归，加上递归结果
            sum += isLeaf(root.left) ? root.left.val : getSum(root.left);
        }
        //有右孩子
        //只有右孩子不是叶子的时候才有可能再加
        if(root.right != null && !isLeaf(root.right)){
            sum += getSum(root.right);
        }
        return sum;
    }

    //判断是否为叶子结点
    public boolean isLeaf(TreeNode root){
        return root.left == null && root.right == null;
    }
}

在 Java 中，Queue 接口提供了以下可直接使用的方法：

  1. offer(E e): 将元素 e 插入队列的尾部。如果队列已满，将返回 false。
  2. poll(): 移除并返回队列头部的元素。如果队列为空，将返回 null。
  3. peek(): 返回队列头部的元素，但不移除它。如果队列为空，将返回 null。
  4. isEmpty(): 判断队列是否为空。如果队列为空，将返回 true；否则返回 false。
  5. size(): 返回队列中元素的个数。

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        //要判空
        if(root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int sum = 0;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                if(isLeaf(node.left)){
                    sum += node.left.val;
                }else{
                    queue.offer(node.left);
                }
            }

            if(node.right != null && !isLeaf(node.right)){
                queue.offer(node.right);
            }
        }
        return sum;
    }

    //判断是否为叶子结点
    public boolean isLeaf(TreeNode root){
        return root.left == null && root.right == null;
    }
}

⑤543.二叉树的直径

题目：给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root。
两节点之间路径的 长度 由它们之间边数表示。

思考：
二叉树的直径 = 经过最大结点数 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //记录经过的结点数的最大值
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        //返回最长路径的长度
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }
}

⑥563.二叉树的坡度

题目：给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //左右子结点的坡度
        int leftSum = getSum(root.left);
        int rightSum = getSum(root.right);
        //根结点的坡度
        int tilt = Math.abs(leftSum - rightSum);
        //返回树的坡度
        return tilt + findTilt(root.left) + findTilt(root.right);
    }

    //得到二叉树中所有结点的值的和
    public int getSum(TreeNode root) {
        if (root == null) {
            return 0;
        } 
        int leftSum = getSum(root.left);
        int rightSum = getSum(root.right);
        return root.val + leftSum + rightSum;
    }
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int ans = 0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return ans;
    }
    //深度优先搜索
    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int sumLeft = dfs(node.left);
        int sumRight = dfs(node.right);

        ans += Math.abs(sumLeft - sumRight);

        return sumLeft + sumRight + node.val;
    }
}

⑦637.二叉树的层平均值

题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案可以被接受。

思考：
深度优先：
counts:每层结点的个数
sums：每层结点值的和
level：控制层数

如果level层数 < sum.size()，表明当前层还没有遍历完(当前层级已经存在于 sums 列表中)，需要在 sum 和 count 的指定位置再加

如果level层数 ≥ sum.size()，是新的一层(当前层级还不存在于 sums 列表中)，直接在 sum 和 count 添加新的一层

接着递归下一层

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //每层结点的个数
        List<Integer> counts = new ArrayList<Integer>();
        //每层结点值的和
        List<Double> sums = new ArrayList<Double>();
        dfs(root,0,counts,sums);

        //每层结点的平均值
        List<Double> averages = new ArrayList<Double>();
        for(int i = 0; i < sums.size(); i++){
            averages.add(sums.get(i) / counts.get(i));
        }
        return averages;
    }

    public void dfs(TreeNode root,int level, List<Integer> counts,List<Double> sums){
        //空节点结束
        if(root == null){
            return;
        }
        //当前层级已经存在于 sums 列表中，当前层还没有遍历完
        if(level < sums.size()){
            //指定位置 加和，个数加一
            sums.set(level,sums.get(level) + root.val);
            counts.set(level,counts.get(level) + 1);
        }else{
            //是新的一层(当前层级还不存在于 sums 列表中)
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left,level + 1,counts,sums);
        dfs(root.right,level + 1,counts,sums);
    }
}

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Double> averageOfLevels(TreeNode root) {
        List<Double> average = new ArrayList<Double>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);
        while(!queue.isEmpty()){
            double sum = 0;
            //当前层结点个数
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            average.add(sum / size);
        }
        return average;
    }

⑧671.二叉树中第二小的节点

题目：给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
如果第二小的值不存在的话，输出 -1 。

特殊.png

思考：
二叉树根节点的值是最小的
第二小：严格大于根节点值

深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
        int ans;
        int rootValue;

    public int findSecondMinimumValue(TreeNode root) {
        ans = -1;
        rootValue = root.val;
        //要找到严格大于rootValue的最小值
        dfs(root);
        return ans;
    }


    public void dfs(TreeNode node){
        if(node == null){
            return;
        }
        //ans已经被更新了，但是不是当前最小的
        if(ans != -1 && node.val >= ans ){
            return;
        }
        //ans未被更新，或者是比当前更新了的最小值还要小
        //当前结点的值严格大于rootValue的值
        if(node.val > rootValue){
            if(ans == -1 || node.val < ans){ //可以不加这层if，上面的if已经排除了
                ans = node.val;
            }
        }
        dfs(node.left);
        dfs(node.right);
    }
}

⑨501.二叉搜索树中的众数

题目：给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。

思考：
二叉排序树的性质：中序遍历非空的二又排序树所得到的数据元素序列是一个按关键字排列的递增有序序列
重复的数字会集中在一起

为了开辟空间单独存储中序遍历结果，可以在递归进行中序遍历的过程中当访问到某个结点时直接对其进行操作

base 当前数字
count 当前数字出现的次数

maxCount 当前出现最多的次数
answer 出现的众数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    List<Integer> answer = new ArrayList<Integer>();//最终答案众数
    int base,count; //当前结点上的数字，及其出现的次数
    int maxCount; //当前出现最多的次数

    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] result = new int[answer.size()];
        for(int i = 0; i < answer.size(); i++){
            result[i] = answer.get(i);
        }
        return result;
    }

    //中序遍历
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        update(root.val);
        dfs(root.right);
    }

    //更新
    public void update(int x){
        if(x == base){
            count++; //数字相同继续加1
        }else{//不同则更新
            base = x;
            count = 1;
        }

        //可能有多个众数
        if(count == maxCount){
            answer.add(base);
        }

        if(count > maxCount){
            //更新最大次数
            maxCount = count;
            //清空answer
            answer.clear();
            //将当前最多次数的数字加入answer
            answer.add(base);
        }
    }
}

⑩530.二叉搜索树的最小绝对差

题目：给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

思考：
考虑对升序数组求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    int minR;
    int pre;
    public int getMinimumDifference(TreeNode root) {
        minR = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return minR;
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }

        dfs(root.left);
        if(pre == -1){
            pre = root.val;
        }else{
            minR = Math.min(minR,root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信