感觉一天一道剑指offer题不够,就再加上一天一道leetcode吧
题目:
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.
给定一棵二叉树,求出它的最小深度。最小深度是从根节点到最近的叶节点的最短路径上的节点数。
思路:
5种情况:空树;没有子树;只有左/右子树;有俩子树
本题要注意最小深度与最大深度的区别:对于最大深度,不需要考虑当前子树是否为单子树(即一侧子树深度为0)的情况,即最大深度一直等于左右子树的最大值;对于最小深度,需要考虑当前子树是否为单子树的情况,对于双子树,其最小深度为左右子树的最小值,对于单子树,其最小深度为左右深度的最大值(因为有一侧的子树为0)。
可采用层序遍历和深度优先遍历,这题的话层序遍历效率高一点,因为若是找到一个叶子节点那么肯定是最短的,无需遍历所有节点,贴的代码用的递归
二叉树操作主要还是利用尾递归或者循环遍历这两种思路,进而涉及DFS(主要利用递归或者栈实现)或者BFS(主要利用队列实现)。剩下的只需要按照这些思路即可。
public class Solution {
public int run(TreeNode root) {
if(root==null)
return 0;
if(root.left==null && root.right==null)
return 1;
if(root.left==null || root.right==null)
return Math.max(run(root.left),run(root.right))+1;
return Math.min(run(root.left),run(root.right))+1;
}
}
网友评论