南京网络推广网站建设公司网站建设核心

Problem: 111. 二叉树的最小深度

题目描述

思路

1.欲望求出最短的路径，先可以记录一个变量minDepth，同时记录每次当前节点所在的层数currentDepth
2.在递的过程中，每次递一层，也即使当前又往下走了一层，则currentDepth++，当到达叶子节点时，比较并取出min【minDepth, currentDepth】
3.在归的过程中，因为是在往上层归，则currentDepth–；
4.返回最终的minDepth即可

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$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--;}
}