Minimum Depth of Binary Tree leetcode java

题目：

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.

题解：

递归解法急速判断左右两边子树哪个depth最小，要注意如果有个节点只有一边孩子时，不能返回0，要返回另外一半边的depth。

递归解法：

     public int minDepth(TreeNode root) {

         if(root == null)

             return 0;

         int minleft = minDepth(root.left);

         int minright = minDepth(root.right);

         if(minleft==0 || minright==0)

             return minleft>=minright?minleft+1:minright+1;

         return Math.min(minleft,minright)+1;

     }

非递归解法：

 1     public int minDepth(TreeNode root) {

 2         if(root == null)

 3             return 0;

 4         

 5         int depth = 1;//The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

 6         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

 7         queue.add(root);

 8         int curnum = 1;

 9         int nextnum = 0;

         while(!queue.isEmpty()){

             TreeNode cur = queue.poll();

             curnum--;

             

             if(cur.left == null && cur.right == null)

                 return depth;

             

             if(cur.left != null){

                queue.add(cur.left);

                nextnum++;

             }

             

             if(cur.right != null){

                 queue.add(cur.right);

                 nextnum++;

             }

             

             if(curnum == 0){

                 curnum = nextnum;

                 nextnum = 0;

                 depth++;

             }

         }

         return depth;

     }

巴特西

Minimum Depth of Binary Tree leetcode java

最新文章

热门文章