【LeetCode】Minimum Depth of Binary Tree 二叉树的最小深度 java

浏览数：49 / 时间：2015年06月08日

【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 }