题目链接

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

描述

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

示例

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

代码

递归

自底向上的思想

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public int maxDepth(TreeNode root) {return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

迭代

也可以用队列迭代解决，但是效率不如递归

class Solution {public int maxDepth(TreeNode root) {//return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()) {for (int i = queue.size(); i > 0; i--){TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}depth++;}return depth;}
}