题目描述
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
递归法：
/*** Definition for binary tree* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
public class Solution {public int run(TreeNode root) {if(root == null)return 0;if(root.left == null && root.right == null)return 1;if(root.left == null)return run(root.right)+1;if(root.right == null)return run(root.left)+1;return Math.min(run(root.left),run(root.right)) + 1;}
}
非递归法：利用树的层次遍历，第一次出现左右子节点都为空的节点为所需要找的节点，此节点为最近叶子节点，根节点到此节点的高度为树的最小深度。
/*** Definition for binary tree* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
import java.util.Queue;
import java.util.LinkedList;public class Solution {public int run(TreeNode root) {if(root == null)return 0;if(root.left == null && root.right == null)return 1;int depth = 0; //记录层数遍历的深度Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();depth++;//len表示树的每一层的节点数for(int i = 0; i < len; i++){TreeNode node = queue.poll();if(node.left == null && node.right == null)return depth;if(node.left != null)queue.offer(node.left);if(node.right != null)queue.offer(node.right);}}return depth;}
}