24.二叉树的最小深度-LeetCode-Java

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最小深度 2. /** * 方法一：层次遍历,访问每一层depth++,直到访问到某一层的元素是叶子节点 */ class Solution { int depth = 1; Queue queue = new LinkedList(); public int minDepth(TreeNode root) { if (root == null) return 0; return levelOrder(root); } private int levelOrder(TreeNode root) { queue.add(root); while (!queue.isEmpty()) { int count = queue.size(); for (int i = 0; i < count; i++) { TreeNode node = (TreeNode) queue.poll(); if (node.left == null && node.right == null) return depth; if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } depth++; } return depth; } } /** * 方法二：递归(分治思想) * 分支有两种情况： * 1：当有分支为null时, DL/DR至少有一个为0,最小深度 = 1 + Math.max(DL,DR); * 2: 当分支都不为null, 最小深度 = 1 + Math.min(DL,DR) */ class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; int DL = minDepth(root.left); int DR = minDepth(root.right); if (root.left == null || root.right == null) return 1 + DL + DR; else return 1 + Math.min(DL, DR); } }