递归思路
可以说是树递归的经典问题了,很多人的递归启蒙应该就是求树的高度…
递归的写法是基于后序遍历的dfs,代码的核心思想是:
1)分别递归求得左子树和右子树的最大深度;
2)比较左右子树的最大深度,取其中较大的那个;
3)加上当前层的深度(+1)。
麻雀虽小,五脏俱全
递归代码
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
非递归思路
当然如果你觉得递归解法太俗的话也可以选择更新(ma)颖(fan)的非递归方法。
思路:
借助队列的广度优先遍历方法,每进行一层遍历就使计数 ++ ,直至队列中所有节点都已出队
C++代码
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)return 0;
queue<TreeNode*> q;
int count = 0;
q.push(root);
while(!q.empty()){
int len = q.size();
//一层一层地进行遍历,len为当前层的节点数量
for(int i = 0; i < len; i ++ ){
TreeNode* temp = q.front();
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
count ++ ;
}
return count;
}
};