代码随想录-Day16

104. 二叉树的最大深度

方法一：深度优先搜索

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

这段代码定义了一个名为 Solution 的类，其中包含一个方法 maxDepth 用于计算二叉树的最大深度。最大深度是从根节点到最远叶子节点的最长路径上的边数。方法使用了递归的策略来实现这一计算。以下是代码的详细解析：

• 方法签名:

  public int maxDepth(TreeNode root)
  

• 输入参数:
  TreeNode root - 二叉树的根节点。
• 输出:
  返回类型为 int 的最大深度值。

代码逻辑:

1. 基本情况处理:

   • 首先检查根节点 root 是否为空 (if (root == null) )。如果树为空，则没有节点，深度为0，所以直接返回0。

2. 递归计算左右子树深度:

   • 如果根节点不为空，递归地计算左子树的最大深度 (int leftHeight = maxDepth(root.left);) 和右子树的最大深度 (int rightHeight = maxDepth(root.right);)。

3. 确定整棵树的最大深度:

   • 使用 Math.max(leftHeight, rightHeight) 来获取左、右子树中较大的深度值，然后加1（因为要包括根节点的高度），得到整棵树的最大深度。
   • 最后，返回这个计算出的最大深度值。

通过递归调用，该方法能够遍历到二叉树的每一个节点，并通过比较左右子树的深度来确定整棵树的最大深度，是一种分治策略的典型应用。

方法二：广度优先搜索

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;}
}

这段代码定义了一个名为 Solution 的类，其中包含一个方法 maxDepth 用于计算二叉树的最大深度，即树中最长路径的边数。这里使用了广度优先搜索（BFS）策略来实现，具体解析如下：

• 方法签名:

  public int maxDepth(TreeNode root)
  

• 输入参数:
  TreeNode root - 二叉树的根节点。
• 输出:
  返回类型为 int 的最大深度值。

代码逻辑:

1. 基本情况处理:

   • 首先检查根节点 root 是否为空 (if (root == null) )。如果是，表明树为空，深度为0，直接返回0。

2. 初始化队列与广度优先遍历:

   • 创建一个队列 queue，并将根节点 root 入队列 (queue.offer(root);)，用于开始广度优先遍历。
   • 定义一个变量 ans 用于存储当前已遍历的层数，初始化为0。
   • 当队列非空时，进行循环，意味着还有节点未遍历：
     • 获取当前层的节点数 size，即队列的大小。
     • 通过内层循环遍历当前层的所有节点：
       • 弹出队首节点 node，处理该节点（实际上这里直接弹出，没有具体操作，重点在于处理其子节点）。
       • 若该节点的左子节点不为空，则左子节点入队列。
       • 若该节点的右子节点不为空，则右子节点入队列。
       • size 减1，表示当前层的一个节点已被处理完毕。
     • 当一层处理完后，ans 增加1，表示已遍历完一层。

3. 返回结果:

   • 当所有节点遍历完毕，队列为空时，返回 ans 作为最大深度。

此算法通过BFS遍历二叉树，每遍历完一层深度加1，最终得到的 ans 即为树的最大深度，这种方式适用于任何形态的二叉树结构，包括不平衡树。

111. 二叉树的最小深度

方法一：深度优先搜索

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;}
}

这段代码是 Java 语言实现的一个解决方案，用于计算二叉树的最小深度。给定一个二叉树，最小深度是从根节点到最近叶子节点的最短路径上的边数。这里使用了递归的方法来解决这个问题。下面是对代码的详细解释：

• public int minDepth(TreeNode root) 定义了一个公开方法，接受一个 TreeNode 类型的参数 root，表示二叉树的根节点，返回值为最小深度。

• 首先检查 root == null，如果根节点为空，则说明这是一个空树，其深度为 0，所以返回 0。

• 然后检查 root.left == null && root.right == null，如果当前节点既没有左子节点也没有右子节点，说明当前节点就是叶子节点，此时深度为 1，所以返回 1。

• 接下来定义一个变量 min_depth 初始化为 Integer.MAX_VALUE，用于保存左右子树中的最小深度。

• 通过条件语句 if (root.left != null) 检查左子节点是否存在，如果存在，则递归调用 minDepth(root.left) 获取左子树的最小深度，并更新 min_depth 的值。

• 同样，通过条件语句 if (root.right != null) 检查右子节点是否存在，如果存在，则递归调用 minDepth(root.right) 获取右子树的最小深度，并更新 min_depth 的值。

• 最后，返回 min_depth + 1 作为整棵树的最小深度。这里的 “+1” 是因为需要加上从父节点到当前节点的这一边。

整个函数通过递归遍历整棵二叉树，逐步计算并比较左右子树的最小深度，从而找到从根节点到最近叶子节点的最短路径长度。

方法二：广度优先搜索

class Solution {class QueueNode {TreeNode node;int depth;public QueueNode(TreeNode node, int depth) {this.node = node;this.depth = depth;}}public int minDepth(TreeNode root) {if (root == null) {return 0;}Queue<QueueNode> queue = new LinkedList<QueueNode>();queue.offer(new QueueNode(root, 1));while (!queue.isEmpty()) {QueueNode nodeDepth = queue.poll();TreeNode node = nodeDepth.node;int depth = nodeDepth.depth;if (node.left == null && node.right == null) {return depth;}if (node.left != null) {queue.offer(new QueueNode(node.left, depth + 1));}if (node.right != null) {queue.offer(new QueueNode(node.right, depth + 1));}}return 0;}
}

这段代码同样实现了计算二叉树最小深度的功能，但采用的是广度优先搜索（BFS）的方法，而非之前的深度优先搜索（DFS）。下面是代码的解释：

• 首先定义了一个内部类 QueueNode，它包含两个成员变量：一个 TreeNode node 用于存储树的节点，一个 int depth 用于记录该节点到根节点的距离（深度）。

• public int minDepth(TreeNode root) 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点，返回值为最小深度。

• 如果根节点为空，返回 0，表示空树。

• 创建一个队列 Queue<QueueNode> queue 来进行广度优先搜索，并初始化一个 QueueNode 对象，包含根节点及其深度 1，然后将此对象加入队列。

• 使用 while 循环处理队列直到其为空。在每次循环中：

  • 弹出队列头部的 QueueNode，获取其中的节点 node 和当前深度 depth。
  • 如果当前节点 node 无左右子节点，即为叶子节点，直接返回当前深度 depth 作为最小深度。
  • 若当前节点有左子节点，创建一个新的 QueueNode 对象，包含左子节点和当前深度加 1，然后将其加入队列。
  • 若当前节点有右子节点，创建一个新的 QueueNode 对象，包含右子节点和当前深度加 1，同样将其加入队列。

• 当队列变空时，理论上不应该发生，因为只要有叶子节点就应该提前返回结果。但为了保持函数返回类型一致性，这里返回 0。在实际应用中，这个返回 0 的情况应该永远不会被执行到，因为一旦发现叶子节点就会立即返回其深度。

通过广度优先搜索，这个算法能够遍历每一层的节点，当遇到第一个没有子节点（即叶子节点）的节点时，就可以确定这是到根节点的最短路径，从而得到最小深度。

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

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

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

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;}
}

这段代码是用来解决一个二叉树问题的，具体问题是计算完全二叉树中的节点个数。完全二叉树是每一层（除了可能的最后一层外）都完全填充的树，并且所有结点都尽可能地集中在左侧。代码采用了两种方法结合的策略：首先通过高度来定位最后一个非空节点所在的层数，然后在一个可能的范围内利用二分查找确定实际的节点数量。下面是详细的解释：

• public int countNodes(TreeNode root) 方法是主要的接口，接收一个 TreeNode 类型的参数 root，表示二叉树的根节点，返回值为树中的节点总数。

• 首先，如果根节点为空，直接返回 0，因为空树没有节点。

• 接着，通过一个循环计算树的高度（层数），同时找到最后一层的第一个节点。level 初始化为 0，node 初始化为 root，循环条件是 node.left != null，意味着只要当前节点有左子节点，就继续向左下移动并增加层数。

• 计算出 level 后，可以推断出这棵完全二叉树节点数量的大致范围：至少有 low = 1 << level 节点（即2的level次方），最多有 high = (1 << (level + 1)) - 1 节点。这里利用位运算快速计算2的幂次。

• 然后，在 low 和 high 之间使用二分查找确定实际的节点数量。在循环中，首先计算中间值 mid，然后调用 exists() 函数检查在这个位置上是否存在节点。根据 exists() 的返回值调整查找范围：如果节点存在，则说明实际节点数至少为 mid，因此更新 low = mid；否则，节点不存在，说明实际节点数小于 mid，则更新 high = mid - 1。

• 当 low >= high 时，二分查找结束，返回 low 作为完全二叉树的确切节点数。

• public boolean exists(TreeNode root, int level, int k) 是一个辅助函数，用来判断在给定层级 (level) 和位置 (k) 是否存在节点。它模拟从根节点开始，根据二进制位确定向左还是向右走，逐步向下查找。bits 变量用于控制每一步的移动方向，初始值为 1 << (level - 1)，表示在当前层级上最左边的节点所对应的二进制位。随着循环的进行，bits 右移一位，直到为0，表示已经到达目标层级并完成查找。如果最终 node 不为空，说明对应位置的节点存在，返回 true；否则，返回 false。

这种解法巧妙地结合了树的高度信息与二分查找的效率，可以在对数时间内解决问题，对于大规模的完全二叉树特别有效。