「leetcode」104&559：求树的最大深度

二叉树和N叉树的最大深度可以通过递归或迭代方法求解。递归方法通过计算左右子树的最大深度加1得到当前树的深度；迭代方法通过层序遍历统计层数得到最大深度。

• 递归法（二叉树）：

  参数和返回值：参数为树的根节点，返回值为树的深度（int）。

  终止条件：如果节点为空，返回0。

  单层递归逻辑：计算左子树和右子树的深度，取较大值加1作为当前节点的深度。

  代码示例：

  class Solution {public: int maxDepth(TreeNode* root) { if (root == NULL) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); }};

• 迭代法（二叉树）：

  层序遍历：使用队列进行层序遍历，每遍历一层，深度加1。

  代码示例：

  class Solution {public: int maxDepth(TreeNode* root) { if (root == NULL) return 0; int depth = 0; queue<TreeNode*> que; que.push(root); while (!que.empty()) { int size = que.size(); depth++; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return depth; }};

• 递归法（N叉树）：

  参数和返回值：参数为N叉树的根节点，返回值为树的深度（int）。

  终止条件：如果节点为空，返回0。

  单层递归逻辑：遍历所有子节点，计算子节点的最大深度，加1作为当前节点的深度。

  代码示例：

  class Solution {public: int maxDepth(Node* root) { if (root == NULL) return 0; int depth = 0; for (int i = 0; i < root->children.size(); i++) { depth = max(depth, maxDepth(root->children[i])); } return depth + 1; }};

• 迭代法（N叉树）：

  层序遍历：使用队列进行层序遍历，每遍历一层，深度加1。

  代码示例：

  class Solution {public: int maxDepth(Node* root) { if (root == NULL) return 0; queue<Node*> que; que.push(root); int depth = 0; while (!que.empty()) { int size = que.size(); depth++; for (int i = 0; i < size; i++) { Node* node = que.front(); que.pop(); for (int j = 0; j < node->children.size(); j++) { if (node->children[j]) que.push(node->children[j]); } } } return depth; }};

总结：

• 递归法：适用于二叉树和N叉树，通过递归计算子树深度，逻辑清晰但可能栈溢出。
• 迭代法：通过层序遍历统计层数，适用于二叉树和N叉树，避免了递归的栈溢出问题，但需要额外的队列空间。

两种方法各有优劣，递归法代码简洁，迭代法更稳定。根据具体场景选择合适的方法。