首页 > 代码库 > 递归的应用--求二叉树最大深度和最小深度
递归的应用--求二叉树最大深度和最小深度
【求最大深度】Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
这里说的最大深度是指最深叶子节点到根节点的路径长度<span style="font-size:18px;"> public static int maxDepth(TreeNode root) { if(root==null)return 0; if(root.right==null && root.left==null)return 1; else return 1+Math.max(maxDepth(root.right), maxDepth(root.left)); }</span>
【求最小深度】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.
这里说的最小深度是指最浅叶子节点到根节点的路径长度,求最小深度相对最大深度来讲要麻烦一点点。
<span style="font-size:18px;"> public static int minDepth(TreeNode root) { if(root==null)return 0; if(root.right==null && root.left==null)//没有子节点 { return 1; } else if(root.right!=null && root.left!=null)//左右儿子都存在 { return Math.min( 1+minDepth(root.left),1+minDepth(root.right)); } else if(root.right==null)//只有左儿子 { return 1+minDepth(root.left); } else { return 1+minDepth(root.right);//只有右儿子 } }</span>
递归的应用--求二叉树最大深度和最小深度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。