categories: [Blog,Algorithm]

104. 二叉树的最大深度

难度简单806
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int maxDepth1(TreeNode root) {
  18.         if (root == null) {
  19.             return 0;
  20.         } else {
  21.             int leftHeight = maxDepth(root.left);
  22.             int rightHeight = maxDepth(root.right);
  23.             return Math.max(leftHeight, rightHeight) + 1;
  24.         }
  25.     }
  26. }
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int maxDepth(TreeNode root) {
  18.         if (root == null) {
  19.             return 0;
  20.         }
  21.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  22.         queue.offer(root);
  23.         int ans = 0;
  24.         while (!queue.isEmpty()) {
  25.             int size = queue.size();
  26.             while (size > 0) {
  27.                 TreeNode node = queue.poll();
  28.                 if (node.left != null) {
  29.                     queue.offer(node.left);
  30.                 }
  31.                 if (node.right != null) {
  32.                     queue.offer(node.right);
  33.                 }
  34.                 size--;
  35.             }
  36.             ans++;
  37.         }
  38.         return ans;
  39.     }
  40. // 作者：LeetCode-Solution
  41. // 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
  43. }

广度优先搜索

思路与算法
我们也可以用「广度优先搜索」的方法来解决这道题目，但我们需要对其进行一些修改，此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量 ans 来维护拓展的次数，该二叉树的最大深度即为 ans。