题解 | #二叉树的最小深度#
二叉树的最小深度
http://www.nowcoder.com/practice/e08819cfdeb34985a8de9c4e6562e724
很简单的一道题,直接深搜就行;
设置一全局变量,记录最小深度;
深搜遇叶子节点,更新最小深度;
为了降低复杂度,剪枝部分分支;
代码如下
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { public int min = Integer.MAX_VALUE; public int run (TreeNode root) { if (root==null) return 0; dfs(root,1); return min; } private void dfs(TreeNode node, int depth) { if (node.left==null&&node.right==null){ min=min>depth?depth:min;//更新最小深度 return; } if (depth>min) return;//剪枝 if (node.left!=null){ dfs(node.left,depth+1); } if (node.right!=null){ dfs(node.right,depth+1); } } }