前言

代码随想录算法训练营day16

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

1.题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

3

/ \ 9 20 / \ 15 7

返回它的最大深度 3 。

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree

2.解题思路

解题思路

1. 标签：DFS
2. 找出终止条件：当前节点为空
3. 找出返回值：节点为空时说明高度为 00，所以返回 00，节点不为空时则分别求左右子树的高度的最大值，同时加 11 表示当前节点的高度，返回该数值
4. 某层的执行过程：在返回值部分基本已经描述清楚
5. 时间复杂度：O(n)O(n)

3.代码实现

```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { if(root == null) { return 0; } else { int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; } } }

```

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

1.题目

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔(请参见示例)。

示例 1：

输入：root = [1,null,3,2,4,null,5,6] 输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5

提示：

1. 树的深度不会超过 1000 。
2. 树的节点数目位于 [0, 104] 之间。

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree

2.解题思路

方法一：深度优先搜索

如果根节点有 NN 个子节点，则这 NN 个子节点对应 NN 个子树。记 NN 个子树的最大深度中的最大值为 maxChildDepthmaxChildDepth，则该 NN 叉树的最大深度为 maxChildDepth+1maxChildDepth+1。

每个子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法计算 NN 叉树的最大深度。具体而言，在计算当前 NN 叉树的最大深度时，可以先递归计算出其每个子树的最大深度，然后在 O(1)O(1) 的时间内计算出当前 NN 叉树的最大深度。递归在访问到空节点时退出。

3.代码实现

```java class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } int maxChildDepth = 0; List children = root.children; for (Node child : children) { int childDepth = maxDepth(child); maxChildDepth = Math.max(maxChildDepth, childDepth); } return maxChildDepth + 1; } }

```

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

1.题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

提示：

1. 树中节点数的范围在 [0, 105] 内
2. -1000 <= Node.val <= 1000

2.解题思路

方法一：深度优先搜索

首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。

对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

3.代码实现

```java class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; }

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

}

```

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

1.题目

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

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

示例 1：

输入：root = [1,2,3,4,5,6] 输出：6

示例 2：

输入：root = [] 输出：0

示例 3：

输入：root = [1] 输出：1

提示：

1. 树中节点的数目范围是[0, 5 * 104]
2. 0 <= Node.val <= 5 * 104
3. 题目数据保证输入的树是 完全二叉树

2.解题思路

方法一：二分查找 + 位运算

对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是 O(n)O(n)，其中 nn 是二叉树的节点个数。这道题规定了给出的是完全二叉树，因此可以利用完全二叉树的特性计算节点个数。

规定根节点位于第 00 层，完全二叉树的最大层数为 hh。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数 hh。

当 0≤i

当最底层包含 11 个节点时，完全二叉树的节点个数是

∑i=0h−12i+1=2hi=0∑h−12i+1=2h

当最底层包含 2h2h 个节点时，完全二叉树的节点个数是

∑i=0h2i=2h+1−1i=0∑h2i=2h+1−1

因此对于最大层数为 hh 的完全二叉树，节点个数一定在 [2h,2h+1−1][2h,2h+1−1] 的范围内，可以在该范围内通过二分查找的方式得到完全二叉树的节点个数。

具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数 kk，如果第 kk 个节点存在，则节点个数一定大于或等于 kk，如果第 kk 个节点不存在，则节点个数一定小于 kk，由此可以将查找的范围缩小一半，直到得到节点个数。

如何判断第 kk 个节点是否存在呢？如果第 kk 个节点位于第 hh 层，则 kk 的二进制表示包含 h+1h+1 位，其中最高位是 11，其余各位从高到低表示从根节点到第 kk 个节点的路径，00 表示移动到左子节点，11 表示移动到右子节点。通过位运算得到第 kk 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 kk 个节点是否存在。

3.代码实现

```java class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int level = 0; TreeNode node = root; while (node.left != null) { level++; node = node.left; } int low = 1 << level, high = (1 << (level + 1)) - 1; while (low < high) { int mid = (high - low + 1) / 2 + low; if (exists(root, level, mid)) { low = mid; } else { high = mid - 1; } } return low; }

1. public boolean exists(TreeNode root, int level, int k) {
2.     int bits = 1 << (level - 1);
3.     TreeNode node = root;
4.     while (node != null && bits > 0) {
5. if ((bits & k) == 0) {
6.             node = node.left;
7.         } else {
8.             node = node.right;
9.         }
10.         bits >>= 1;
11.     }
12. return node != null;
13. }

}

```