代码随想录训练营二刷第十六天 | 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

代码随想录训练营二刷第十六天 | 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

一、104.二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路：后序遍历，层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}
1
2
3
4
5
6
7
8

二、559.n叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
思路：后序遍历加for

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        if (root.children == null) return 1;
        int max = Integer.MIN_VALUE;
        for (Node child : root.children) {
             max = Math.max(max, maxDepth(child));
        }
        return max == Integer.MIN_VALUE ? 1 : max + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

三、111.二叉树的最小深度

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
思路：这题用层序遍历最快

public int minDepth(TreeNode root) {
        if (root == null) return 0;
        return deep(root);
    }
    int deep(TreeNode root) {
        if (root.left == null && root.right == null) return 1;
        int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
        if (root.left != null) {
            left = minDepth(root.left);
        }
        if (root.right != null) {
            right = minDepth(root.right);
        }
        return Math.min(left, right) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/
思路：从完全二叉树结构出发。

public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left, right = root.right;
        int leftNum = 0, rightNum = 0;
        while (left != null) {
            leftNum++;
            left = left.left;
        }
        while (right != null) {
            rightNum++;
            right = right.right;
        }
        if (leftNum == rightNum) {
            return (2 << leftNum) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17