问题

给定一个二叉树,找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
说明: 叶子节点是指没有子节点的节点

示例:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回它的最大深度 3

解法一:递归

后序遍历,因为要通过递归函数的返回值做计算树的高度
代码的逻辑是求根节点的高度,根节点的高度即为这棵树的最大深度

  1. class Solution {
  2. public int maxDepth(TreeNode root) {
  3. if(root == null){
  4. return 0;
  5. }else{
  6. int leftdepth = maxDepth(root.left);
  7. int rightdepth = maxDepth(root.right);
  8. return Math.max(leftdepth, rightdepth) + 1;
  9. }
  10. }
  11. }

时间复杂度:leetcode-104:二叉树的最大深度 - 图1,其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次
空间复杂度:leetcode-104:二叉树的最大深度 - 图2,其中 height 表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度

解法二:广度优先搜索

  1. package leetcode_104;
  2. import javax.swing.tree.TreeNode;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. public class solution {
  6. public int maxDepth(TreeNode root) {
  7. if (root == null){
  8. return 0;
  9. }
  10. Queue<TreeNode> queue = new LinkedList<TreeNode>();
  11. queue.offer(root);
  12. int depth = 0;
  13. while(!queue.isEmpty()){
  14. int size = queue.size();
  15. for (int i = 0; i < size; i++){
  16. TreeNode node = queue.poll();
  17. if (node.left != null){
  18. queue.offer(node.left);
  19. }
  20. if (node.right != null){
  21. queue.offer(node.right);
  22. }
  23. }
  24. depth += 1;
  25. }
  26. return depth;
  27. }
  28. }

时间复杂度:leetcode-104:二叉树的最大深度 - 图3,其中 n 为二叉树的节点个数,每个节点只会被访问一次
空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到 leetcode-104:二叉树的最大深度 - 图4