当前位置：首页 > news >正文

C++算法练习-day29——104.二叉树的最大深度

news 2024/11/1 6:55:53

题目来源：. - 力扣（LeetCode）

题目思路分析

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。有两种常见的方法来解决这个问题：递归方法和广度优先搜索（BFS）方法。

递归（深度优先搜索（DFS））方法：
- 如果根节点为空，则深度为0。
- 否则，递归地计算左子树和右子树的最大深度，然后取两者中的较大值，并加1（加上根节点）。
广度优先搜索（BFS）方法：
- 使用一个队列来进行层次遍历。
- 将根节点入队。
- 初始化深度计数器为0。
- 当队列不为空时，进入循环：
  - 获取当前层的节点数（即队列的大小）。
  - 遍历当前层的所有节点，并将它们的子节点（如果存在）入队。
  - 每处理完一层，深度计数器加1。
- 当队列为空时，遍历结束，返回深度计数器的值。

代码：

递归（深度优先搜索（DFS））方法：

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  * };  */  
class Solution {  
public:  int maxDepth(TreeNode* root) {  // 如果根节点为空，返回深度0  // 否则，递归计算左右子树的最大深度，并取较大值加1  return !root ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;  }  
};

广度优先搜索（BFS）方法：

/**  * Definition for a binary tree node. (Same as above, omitted for brevity)  */  
class Solution {  
public:  int maxDepth(TreeNode* root) {  // 如果根节点为空，返回深度0  if (!root) {  return 0;  }  // 使用队列进行层次遍历  queue<TreeNode*> Q;  Q.push(root);  // 初始化深度计数器  int ans = 0;  // 当队列不为空时，继续遍历  while (!Q.empty()) {  int sz = Q.size(); // 获取当前层的节点数  // 遍历当前层的所有节点  while (sz > 0) {  TreeNode* p = Q.front(); // 取出队列头部的节点  Q.pop(); // 从队列中移除该节点  // 如果左子节点存在，将其入队  if (p->left) {  Q.push(p->left);  }  // 如果右子节点存在，将其入队  if (p->right) {  Q.push(p->right);  }  sz--; // 减少当前层的节点计数器  }  // 每处理完一层，深度计数器加1  ++ans;  }  // 返回深度计数器的值  return ans;  }  
};

知识点摘要

二叉树：一种树形数据结构，其中每个节点最多有两个子节点（左子节点和右子节点）。
递归：一种在函数内部调用自身的编程技巧，常用于解决可以分解为相似子问题的问题。
深度优先搜索（DFS）：深度优先搜索（DFS）是一种图搜索算法，通过递归或栈实现，沿着图的深度方向尽可能搜索，直到找到目标或遍历完所有顶点。它适用于图遍历、路径查找、连通性检测等多种应用场景。
广度优先搜索（BFS）：一种图搜索算法，从起始节点开始，首先访问所有相邻节点，然后对每个相邻节点重复此过程。
队列：一种先进先出（FIFO）的数据结构，常用于层次遍历和广度优先搜索。

通过递归和广度优先搜索两种方法，我们可以有效地计算二叉树的最大深度。递归方法简洁明了，通过递归地计算左右子树的最大深度来得到整个树的最大深度。广度优先搜索方法则通过层次遍历整个树，逐层计算深度，直到遍历完所有节点。这两种方法各有优缺点，递归方法实现简单但可能导致栈溢出（对于非常深的树），而广度优先搜索方法则使用额外的空间来存储队列中的节点，但避免了递归的深度限制。在实际应用中，可以根据具体情况选择最适合的方法。

查看全文

http://www.mrgr.cn/news/63036.html