二叉树的最大深度会求了，那么顺手把N叉树也做了吧

104.二叉树的最大深度

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

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

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

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

二叉树的最小深度是多少（看看这些树的最大深度）(1)

返回它的最大深度 3 。

思路递归法

本题其实也要后序遍历（左右中），依然是因为要通过递归函数的返回值做计算树的高度。

按照递归三部曲，来看看如何来写。

  1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。

代码如下：

intgetDepth(TreeNode*node)

  1. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。

代码如下：

if(node==NULL)return0;

  1. 确定单层递归的逻辑：先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再 1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

代码如下：（后序遍历，按照左右中的顺序）

intleftDepth=getDepth(node->left);//左 intrightDepth=getDepth(node->right);//右 intdepth=1 max(leftDepth,rightDepth);//中 returndepth;

所以整体C 代码如下：

classSolution{ public: intgetDepth(TreeNode*node){ if(node==NULL)return0; intleftDepth=getDepth(node->left);//左 intrightDepth=getDepth(node->right);//右 intdepth=1 max(leftDepth,rightDepth);//中 returndepth; } intmaxDepth(TreeNode*root){ returngetDepth(root); } };

代码精简之后C 代码如下：

classSolution{ public: intmaxDepth(TreeNode*root){ if(root==NULL)return0; return1 max(maxDepth(root->left),maxDepth(root->right)); } };

「精简之后的代码根本看不出是哪种遍历方式，也看不出递归三部曲的步骤，所以如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。」

迭代法

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

二叉树的最小深度是多少（看看这些树的最大深度）(2)

层序遍历

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

如果对层序遍历还不清楚的话，可以看这篇：二叉树：层序遍历登场

C 代码如下：

classSolution{ public: intmaxDepth(TreeNode*root){ if(root==NULL)return0; intdepth=0; queue<TreeNode*>que; que.push(root); while(!que.empty()){ intsize=que.size(); depth ;//记录深度 for(inti=0;i<size;i ){ TreeNode*node=que.front(); que.pop(); if(node->left)que.push(node->left); if(node->right)que.push(node->right); } } returndepth; } };

那么我们可以顺便解决一下N叉树的最大深度问题

559.N叉树的最大深度

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

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

例如，给定一个 3叉树 :

二叉树的最小深度是多少（看看这些树的最大深度）(3)

我们应返回其最大深度，3。

思路

依然可以提供递归法和迭代法，来解决这个问题，思路是和二叉树思路一样的，直接给出代码如下：

递归法

C 代码：

classSolution{ public: intmaxDepth(Node*root){ if(root==0)return0; intdepth=0; for(inti=0;i<root->children.size();i ){ depth=max(depth,maxDepth(root->children[i])); } returndepth 1; } };

迭代法

依然是层序遍历，代码如下：

classSolution{ public: intmaxDepth(Node*root){ queue<Node*>que; if(root!=NULL)que.push(root); intdepth=0; while(!que.empty()){ intsize=que.size(); vector<int>vec; depth ;//记录深度 for(inti=0;i<size;i ){ Node*node=que.front(); que.pop(); for(inti=0;i<node->children.size();i ){ if(node->children[i])que.push(node->children[i]); } } } returndepth; } };

-------end-------

我将算法学习相关的资料已经整理到了

Github ：https://github.com/youngyangyang04/leetcode-master，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库有空看一看一定会有所收获，顺便给一个star支持一下吧！

我是程序员Carl，哈工大师兄，先后在腾讯和百度打杂，这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！

@代码随想录 期待你的关注

,