您现在的位置是：首页 > 文章详情

【LeetCode-面试算法经典-Java实现】【111-Minimum Depth of Binary Tree（二叉树的最小深度）】

日期：2018-03-30点击：296收藏

原题

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.

题目大意

给定一棵两叉树求树的最小深度。

解题思路

遍历法，对整个树进行遍历，找出最小的深度。

代码实现

树结果定义

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

算法实现类

public class Solution { private int min = Integer.MAX_VALUE; // 记录树的最小深度 private int cur = 0; // i当前处理的树的尝试 public int minDepth(TreeNode root) { depth(root); return min; } /** * 计算树的深度 * * @param node 当前结点 */ private void depth(TreeNode node) { if (node == null) { min = cur; return; } cur++; // 当前处理的层次加1 // 如果是叶节点，并且路径比记录的最小还小 if (node.left == null && node.right == null && cur < min) { min = cur; // 更新最小值 } // 处理左子树 if (node.left != null) { depth(node.left); } // 处理右子树 if (node.right != null) { depth(node.right); } cur--; // 还原 } }

/** * 计算树的深度 * * @param node 当前结点 */ private void depth (TreeNode node) { if (node == null ) { min = cur; return ; } cur++; // 当前处理的层次加1 // 如果是叶节点，并且路径比记录的最小还小 if (node.left == null && node.right == null && cur < min) { min = cur; // 更新最小值 } // 处理左子树 if (node.left != null ) { depth(node.left); } // 处理右子树 if (node.right != null ) { depth(node.right); } cur--; // 还原 }}

原文链接：https://yq.aliyun.com/articles/577754

关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有，本站原创内容转载请注明来源。