网站收录大量下降,一个网站建设的课程设计书,网站建设教程视频西瓜,游戏软件开发培训学校Problem: 111. 二叉树的最小深度 文章目录 题目描述思路复杂度Code 题目描述 思路 1.欲望求出最短的路径#xff0c;先可以记录一个变量minDepth#xff0c;同时记录每次当前节点所在的层数currentDepth 2.在递的过程中#xff0c;每次递一层#xff0c;也即使当前又往下走… Problem: 111. 二叉树的最小深度 文章目录 题目描述思路复杂度Code 题目描述 思路 1.欲望求出最短的路径先可以记录一个变量minDepth同时记录每次当前节点所在的层数currentDepth 2.在递的过程中每次递一层也即使当前又往下走了一层则currentDepth当到达叶子节点时比较并取出min【minDepth, currentDepth】 3.在归的过程中因为是在往上层归则currentDepth– 4.返回最终的minDepth即可 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为二叉树的节点个数 空间复杂度: O ( h ) O(h) O(h)最坏空间复杂度 Code
DFS
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {// record the minimum depth private int minDepth Integer.MAX_VALUE;// record the depth of the current node being traversedprivate int currentDepth 0;public int minDepth(TreeNode root) {if (root null) {return 0;}// start DFS traverssal from the root nodetravers(root);return minDepth;}private void travers(TreeNode root) {if (root null) {return;}// increase the current depth when entering a node in the preorder positioncurrentDepth;// if the current node is a leaf, update the minimum depthif (root.left null root.right null) {minDepth Math.min(minDepth, currentDepth);}travers(root.left);travers(root.right);// decrease the current depth when leaving a node in the postorder positioncurrentDepth--;}
}
