代码随想录打卡

àì夳堔傛蜴生んèń 2024-02-22 09:17 24阅读 0赞

## 前言 ##

代码随想录算法训练营day16

--------------------

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

### 1.题目 ###

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

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

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

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

复制代码

`3`

/  
9 20 /  
15 7

返回它的最大深度 3 。

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/ma…][leetcode.cn_problems_ma]

### 2.解题思路 ###

解题思路

scss

复制代码

`标签：DFS 找出终止条件：当前节点为空 找出返回值：节点为空时说明高度为 00，所以返回 00，节点不为空时则分别求左右子树的高度的最大值，同时加 11 表示当前节点的高度，返回该数值 某层的执行过程：在返回值部分基本已经描述清楚 时间复杂度：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

提示：

css

复制代码

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

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/ma…][leetcode.cn_problems_ma 1]

### 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<Node> 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

提示：

css

复制代码

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

### 2.解题思路 ###

方法一：深度优先搜索

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

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

### 3.代码实现 ###

java

复制代码

`class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int min_depth = Integer.MAX_VALUE; if (root.left != null) { min_depth = Math.min(minDepth(root.left), min_depth); } if (root.right != null) { min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1; } }`

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

### 1.题目 ###

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

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

示例 1：

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

示例 2：

输入：root = \[\] 输出：0

示例 3：

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

提示：

css

复制代码

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

### 2.解题思路 ###

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

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

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

当 0≤i<h0≤i<h 时，第 ii 层包含 2i2i 个节点，最底层包含的节点数最少为 11，最多为 2h2h。

当最底层包含 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; } public boolean exists(TreeNode root, int level, int k) { int bits = 1 << (level - 1); TreeNode node = root; while (node != null && bits > 0) { if ((bits & k) == 0) { node = node.left; } else { node = node.right; } bits >>= 1; } return node != null; } }`

[leetcode.cn_problems_ma]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmaximum-depth-of-binary-tree
[leetcode.cn_problems_ma 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmaximum-depth-of-n-ary-tree