分享程序员开发的那些事...
更新时间：2021-11-19 05:21:12
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
求二叉树的最大深度问题用到深度优先搜索DFS，递归的完美应用，跟求二叉树的最小深度问题原理相同。代码如下：
C++ 解法一：
public: int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } };
Java 解法一：
public class Solution { public int maxDepth(TreeNode root) { return root == null ? 0 : (1 + Math.max(maxDepth(root.left), maxDepth(root.right))); } }
我们也可以使用层序遍历二叉树，然后计数总层数，即为二叉树的最大深度，参见代码如下：
C++ 解法二：
public: int maxDepth(TreeNode* root) { if (!root) return 0; int res = 0; queue<TreeNode*> q; q.push(root); while (!q.empty()) { ++res; int n = q.size(); for (int i = 0; i < n; ++i) { TreeNode *t = q.front(); q.pop(); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } } return res; } };
Java 解法二：
public int maxDepth(TreeNode root) { if (root == null) return 0; int res = 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { ++res; int n = q.size(); for (int i = 0; i < n; ++i) { TreeNode t = q.poll(); if (t.left != null) q.offer(t.left); if (t.right != null) q.offer(t.right); } } return res; } }
求二叉树的最小深度可以参见我的博文：
http://www.cnblogs.com/grandyang/p/4042168.html
参考资料：
https://discuss.leetcode.com/topic/10317/my-code-of-c-depth-first-search-and-breadth-first-search
本文转自博客园Grandyang的博客，原文链接：[LeetCode] Maximum Depth of Binary Tree 二叉树的最大深度
，如需转载请自行联系原博主。