Leetcode#104. Maximum Depth of Binary Tree（二叉树的最大深度）

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路

思路一：

递归

思路二：

非递归，层次遍历

代码实现

package Tree; import java.util.LinkedList; import java.util.Queue; /** * 104. Maximum Depth of Binary Tree（二叉树的最大深度） * 给定一个二叉树，找出其最大深度。 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 */ public class Solution104 { /** * 递归 * * @param root * @return */ public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1); } /** * 非递归，层次遍历 * * @param root * @return */ public int maxDepth_2(TreeNode root) { if (root == null) { return 0; } int depth = 0; int start = 0; int end = 1; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode temp = queue.poll(); start++; if (temp.left != null) { queue.offer(temp.left); } if (temp.right != null) { queue.offer(temp.right); } if (start == end) { start = 0; end = queue.size(); depth++; } } return depth; } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }