找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1409|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Minimum Depth of Binary Tree】-【刷题第一弹2014】

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 10-12-2014 01:49 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Leetcode通道:https://oj.leetcode.com/problems/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.

思路:BFS 按层遍历记录深度,遇到第一个叶子节点就终止,得到最小路径

代码:

  1. public class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root == null) return 0;
  4.         
  5.         Queue<TreeNode> que = new LinkedList<TreeNode>();
  6.         que.add(root);
  7.         que.add(null);
  8.         
  9.         int depth = 0;
  10.         while(!que.isEmpty()){
  11.             TreeNode cur = que.poll();
  12.             while(cur != null){
  13.                 if(cur.left == null && cur.right == null) return depth + 1;
  14.                 if(cur.left != null) que.add(cur.left);
  15.                 if(cur.right != null) que.add(cur.right);
  16.                 cur = que.poll();
  17.             }
  18.             ++depth;
  19.             if(!que.isEmpty()) que.add(null);
  20.         }
  21.         return depth;
  22.     }
  23. }
复制代码

时间复杂度:O(n), 空间复杂度: O(n)


本帖被以下淘专辑推荐:

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-4-2014 09:57 PM | 显示全部楼层
  1.     public int minDepth(TreeNode root) {
  2.         if(root == null) return 0;
  3.         return helper(root);
  4.     }
  5.     public int helper(TreeNode root){
  6.         if(root.left == null && root.right == null)
  7.             return 1;
  8.         int left = Integer.MAX_VALUE;
  9.         int right = Integer.MAX_VALUE;
  10.         if(root.left != null)
  11.            left = helper(root.left);
  12.         if(root.right != null)
  13.            right = helper(root.right);
  14.         return Math.min(left, right)+1;
  15.     }
  16. 递归解法,时间为O(n), 空间为O(log n)
复制代码


迭代解法,时间为O(n),空间为O(n)
  1.     public int minDepth(TreeNode root) {
  2.         if(root == null) return 0;
  3.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  4.         queue.add(root);
  5.         queue.add(null);
  6.         int level = 1;
  7.         while(!queue.isEmpty()){
  8.             TreeNode tmp = queue.poll();
  9.             if(tmp != null){
  10.                 if(tmp.left == null && tmp.right == null)
  11.                     break;
  12.                 if(tmp.left!=null)
  13.                     queue.add(tmp.left);
  14.                 if(tmp.right!=null)
  15.                     queue.add(tmp.right);
  16.             }
  17.             else if(tmp == null && !queue.isEmpty()){
  18.                 queue.add(null);
  19.                 level++;
  20.             }
  21.             else
  22.                 break;
  23.         }
  24.         return level;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表