首页 > 代码库 > 【LeetCode】Minimum Depth of Binary Tree 二叉树的最小深度 java
【LeetCode】Minimum Depth of Binary Tree 二叉树的最小深度 java
【LeetCode】Minimum Depth of Binary Tree
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.
递归和非递归，此提比较简单。广度优先遍历即可。关键之处就在于如何保持访问深度。
下面是4种代码：
1 import java.util.ArrayList; 2 import java.util.LinkedList; 3 import java.util.List; 4 import java.util.Queue; 5 6 class TreeNode { 7 int val; 8 TreeNode left; 9 TreeNode right; 10 11 TreeNode(int x) { 12 val = x; 13 } 14 } 15 public class MinimumDepthofBinaryTree { 16 /** 17 * 递归深度遍历 18 * @param root 19 * @return 20 */ 21 public int minDepth1(TreeNode root) { 22 if(root==null) 23 return 0; 24 if(root.left==null&&root.right==null){ 25 return 1; 26 } 27 int left=minDepth1(root.left); 28 int right=minDepth1(root.right); 29 if(left==0){ 30 return right+1; 31 } 32 if(right==0){ 33 return left+1; 34 } 35 else{ 36 return Math.min(right, left)+1; 37 } 38 } 39 public int minDepth2(TreeNode root) { 40 if(root==null) 41 return 0; 42 int left=minDepth1(root.left); 43 int right=minDepth1(root.right); 44 45 if(left==0&&right==0){ 46 return 1; 47 } 48 if(left==0){ 49 right= Integer.MAX_VALUE; 50 } 51 if(right==0){ 52 left=Integer.MAX_VALUE; 53 } 54 55 return Math.min(right, left)+1; 56 57 } 58 59 /** 60 * 广度优先搜索。一旦发现叶子结点，返回遍历深度。 61 * @param root 62 * @return 63 */ 64 public int minDepth3(TreeNode root) { 65 if(root==null){ 66 return 0; 67 } 68 Queue<TreeNode>queue=new LinkedList<>(); 69 queue.add(root); 70 int count=queue.size();//用来保存访问当前层次剩余未访问的节点。 71 int depth=1;//用来保存二叉树的访问深度 72 while(!queue.isEmpty()){ 73 //广度遍历 74 TreeNode topNode=queue.poll(); 75 count--; 76 if(topNode.left!=null){ 77 queue.add(topNode.left); 78 } 79 if(topNode.right!=null){ 80 queue.add(topNode.right); 81 } 82 //发现叶子节点 83 if(topNode.left==null&&topNode.right==null){ 84 return depth; 85 } 86 //访问一层完毕 87 if(count==0){ 88 depth++; 89 count=queue.size(); 90 } 91 92 } 93 return 0; 94 } 95 /** 96 * 广度优先搜索。一旦发现叶子结点，返回遍历深度。 97 * @param root 98 * @return 99 */100 public int minDepth4(TreeNode root) {101 if(root==null){102 return 0;103 }104 List<TreeNode>list=new ArrayList<>();105 int count=1;106 list.add(root);107 while(list.size()!=0){108 List<TreeNode>singleList=new ArrayList<>();109 for(TreeNode t:list){110 if(t.left!=null){111 singleList.add(t.left);112 }if(t.right!=null){113 singleList.add(t.right);114 }115 if(t.left==null&&t.right==null){116 return count; 117 }118 }119 count++;120 list=singleList;121 }122 return 0;123 }124 public static void main(String[] args) {125 TreeNode rootNode1 = new TreeNode(1);126 TreeNode rootNode2 = new TreeNode(2);127 TreeNode rootNode3 = new TreeNode(3);128 TreeNode rootNode4 = new TreeNode(4);129 TreeNode rootNode5 = new TreeNode(5);130 TreeNode rootNode6 = new TreeNode(6);131 TreeNode rootNode7 = new TreeNode(7);132 rootNode1.left = rootNode2;133 rootNode1.right = rootNode3;134 rootNode2.left = rootNode4;135 rootNode2.right = rootNode5;136 rootNode3.left = rootNode6;137 rootNode3.right = rootNode7;138 MinimumDepthofBinaryTree minimumDepthofBinaryTree=new MinimumDepthofBinaryTree();139 System.out.println(minimumDepthofBinaryTree.minDepth4(rootNode1));140 141 }142 143 }
【LeetCode】Minimum Depth of Binary Tree 二叉树的最小深度 java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。