题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
方法1：深度优先搜索
原理：深度优先搜索（Depth First Search）是一种遍历图的算法，它从图中的某个顶点出发，沿着一条路径不断向下探索，直到无法继续深入为止，然后回溯到上一个顶点，继续探索其他路径，直到所有顶点都被访问过为止， 所有的顶点都被压入栈中。栈：先进后出。
思路：使用深度优先搜索，遍历整棵树，记录最小的深度。对于每一个非叶子节点，分别计算其左右叶子结点的最小叶子结点深度。通过递归的方式解决该问题。但递归在运行时，值的变化很难把握。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public int minDepth(TreeNode root) { if(root == null){ return 0; } if (root.left == null && root.right == null) { return 1; } // 最小深度 int min_depth = Integer.MAX_VALUE; // 左子树节点 if(root.left != null){ min_depth = Math.min(minDepth(root.left), min_depth); } // 右子树节点 if(root.right != null){ min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1;} |
时间复杂度为O(N)，因为二叉树中，每一个子节点都被访问过。平均空间复杂度O(logN)。
方法2：广度优先搜索
原理：广度优先搜索（Breadth First Search）是一种遍历图的算法，它从图中的某个顶点出发，沿着一条路径不断向下探索，直到无法继续深入为止，然后回溯到上一个顶点，继续探索其他路径，直到所有顶点都被访问过为止， 所有的顶点都被压入队列中。队列：先进先出。
思路：使用广度优先搜索，当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | class QueueNode{ // 定义属性 TreeNode node; int depth; // 构造函数 public QueueNode(TreeNode node,int depth){ this.node = node; this.depth = depth; } } public int minDepth(TreeNode root) { if(root == null){ return 0; } Queuenew LinkedList queue1.offer(new QueueNode(root,1));// 先将第一个根节点放入队列中 while(!queue1.isEmpty()){ // 弹出首个元素 QueueNode nodedepth = queue1.poll(); TreeNode node = nodedepth.node; int depth = nodedepth.depth; if (node.left == null && node.right == null) { // 最终的出口一定在这里 return depth; } // 左子树节点 if(node.left != null){ // 将节点放入队列中 depth = depth + 1 queue1.offer(new QueueNode(node.left,depth + 1)); } // 右子树节点 if(node.right != null){ // 将节点放入队列中 depth = depth + 1 queue1.offer(new QueueNode(node.right,depth + 1)); } } return 0; } |
时间复杂度为O(N)，因为二叉树中，每一个子节点都被访问过。平均空间复杂度O(N)。