首页 > 试题广场 >

二叉树的最小深度

[编程题]二叉树的最小深度
  • 热度指数：185701 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。

示例1

输入

{1,2,3,4,5}

输出

2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
专业陪跑头像 专业陪跑 
//层次遍历 获取第一个叶子节点
    public int run(TreeNode root) {
        if(root==null)
            return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        int level=1;
        TreeNode last,now;
        last=now=root;
        queue.add(root);
        while(queue.size()!=0){
            TreeNode node=queue.poll();
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
            if(node.left==null&&node.right==null)
                return level;
            if(node==last){
                level++;
                last=queue.getLast();
            }


        }
        return level;
    }
发表于 2017-11-15 21:19:14 回复(0)
Java
tornado123头像 tornado123 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int run (TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left != null && root.right != null) {
            return Math.min(run(root.left), run(root.right)) + 1;
        }else if(root.left != null) {
            return run(root.left) + 1;
        }else if(root.right != null) {
            return run(root.right) + 1;
        }else {
            // 该节点为叶子节点
            return 1;
        }
    }
}

发表于 2020-11-28 00:19:11 回复(0)
C/C++
xiaoehaier头像 xiaoehaier 
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int run(TreeNode* root) {
        // write code here
        if(root == nullptr) return 0;
        int l = run(root->left);
        int r = run(root->right);
        
        return 1 + (l&&r ? min(l,r) : l^r);
    }
};


发表于 2020-07-06 22:44:43 回复(1)
Java
枫叶@头像 枫叶@
第一种使用递归思想：
public class Solution {
    public int run(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null){
            return 1 + run(root.right);
        }
        if(root.right == null){
            return 1 + run(root.left);
        }
        return 1 + Math.min(run(root.right),run(root.left));
    }
}

第二种使用层序遍历思想：
import java.util.*;
public class Solution {
    public int run(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null)
            return 1;
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int count=0;
        while(!queue.isEmpty()){
            int len=queue.size();
            count++;
            for(int i=0; i<len; i++){
                TreeNode temp=queue.remove(0);
                if(temp.left==null&&temp.right==null)
                    return count;
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
        }
        return count;
    }
}

编辑于 2019-03-07 22:20:32 回复(0)
吾生有你头像 吾生有你
纪念一下：从今后，我要好好刷题，再也不浪了 
import java.util.*;
public class Solution {
    public int run(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null)
            return 1;
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int count=0;
        while(!queue.isEmpty()){
            int len=queue.size();
            count++;
            for(int i=0; i<len; i++){
                TreeNode temp=queue.remove(0);
                if(temp.left==null&&temp.right==null)
                    return count;
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
        }
        return count;
    }
}

编辑于 2018-07-28 19:12:00 回复(0)
此广告位出租头像 此广告位出租
没错，就是找一个叶子结点 
import java.util.LinkedList;
public class Solution {
    public int run(TreeNode root) {
        if (root == null){
			return 0;
		}
		if (root.left==null && root.right==null){
			return 1;
		}
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.addLast(root);
		list.addLast(null);
		int deepth = 1;
		while (!list.isEmpty()){
			TreeNode treeNode = list.pop();
			if (treeNode == null){
				list.addLast(null);
				deepth++;
				continue;
			}
			if (treeNode.left==null && treeNode.right==null){
				return deepth;
			}
			if (treeNode.left != null){
				list.addLast(treeNode.left);
			}
			if (treeNode.right != null){
				list.addLast(treeNode.right);
			}
		}
		return deepth;
    }
}

发表于 2017-09-06 21:51:52 回复(0)
小鸡啄米的嗨皮♛头像 小鸡啄米的嗨皮♛
public class Solution {
    public int run(TreeNode root) {
        if(root == null){
            return 0; 
        }        
        // 只有单个子树的情况
        if (null == root.left){
            return run(root.right) + 1;
        }
        if (null == root.right){
            return run(root.left) + 1;
        }
        
        // 双子树情况
        return Math.min(run(root.left), run(root.right)) + 1;
    }
}
注：求二叉树的最大深度时，只需要考虑节点左右子树的最大值即可，单子树的情况不需要考虑；而二叉树的最小深度，当只有单个子时，子树深度就是最小深度，所以此种情况需要考虑，否则会出现深度为0的问题。
发表于 2016-08-09 22:49:26 回复(0)
Python 3
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
import sys
sys.setrecursionlimit(1000000)

class Solution:
  def run(self , root):
    if root is None:                             return 0
    if root.left is None and root.right is None: return 1
    if root.left is None:                        return 1 + self.run(root.right)
    if root.right is None:                       return 1 + self.run(root.left);
    return 1 + min(self.run(root.left), self.run(root.right))

发表于 2021-07-21 10:02:23 回复(0)
否极泰来……头像 否极泰来…… 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int depth = 0;
    public int run (TreeNode root) {
        // write code here
        if(root == null) {
            return depth;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        run(queue);
        return depth;
    }
    
    public  void run(Queue<TreeNode> queue) {
        int qsize = queue.size();
        if(qsize>0) {
            depth++;
        }else {
            return ;
        }
        while(qsize>0) {
            TreeNode node = queue.poll();
            System.out.println(node.val);
            qsize--;
            if(node.left == null && node.right == null) {
                return;
            }
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
        run(queue);
    }
}

解题思路：利用队列实现广度优先搜索叶子节点（没有子节点的节点，left==null和right==null）
发表于 2021-03-26 10:27:07 回复(0)
sSTtaArR头像 sSTtaArR 
class Solution {
public:
    int run(TreeNode* root) {
        if(root == nullptr) return 0; 
        queue<TreeNode*> q; q.push(root);
        int dep = 1;
        while(!q.empty())
        {
            int s = q.size(); 
            while(s--)
            {
                TreeNode* t = q.front(); q.pop(); 
                if(t->right == nullptr && t->left == nullptr) return dep; 
                if(t->right) q.push(t->right); 
                if(t->left) q.push(t->left); 
            }
            dep++; 
        }
        return dep; 
    }
};

发表于 2021-01-24 21:27:59 回复(0)
C/C++
一路向南_Velscode头像 一路向南_Velscode
DFS深搜。全局变量mindeepth记录最小深度，遇到左右子树皆为NULL的叶子节点时，更新之
注意，判断空树 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int mindeepth = INT_MAX;
    void dfs(TreeNode* root, int deepth) {
        if (root == NULL) { return ; }
        if (root->left == NULL && root->right == NULL) {
            if (deepth < mindeepth) {
                mindeepth = deepth;
            }
        }
        dfs(root->left, deepth +
            1);
        dfs(root->right, deepth + 1);
    }
    int run(TreeNode* root) {
        dfs(root, 1) ;
        return mindeepth == INT_MAX ? 0 : mindeepth;
    }
};


发表于 2020-12-28 15:58:26 回复(0)
C/C++
AKUNAYA头像 AKUNAYA 
        int run(TreeNode* root) {
        // write code here
        if(root==NULL) return 0;
        if(root->left==NULL&&root->right==NULL) return 1;
        if(root->left==NULL&&root->right!=NULL) return 1+run(root->right);
        if(root->left!=NULL&&root->right==NULL) return 1+run(root->left);
        if(root->left!=NULL&&root->right!=NULL) return min(1+run(root->left),1+run(root->right));
    }

编辑于 2020-08-07 14:37:06 回复(0)
Evan_Wang🌴🌴头像 Evan_Wang🌴🌴
这道题和leetcode104不能弄混，这道题是“树的根结点”到”最近叶子结点“的最短路径上结点的数量。不是简单求个最小深度，因此在一棵树上有一端是空另一端不空的情况下，应该返回有非空的那一边的深度。
原本leetcode104的代码，在这里不能通过： 
public static int getMinDepth(Node node) {
    if (node == null) {
        return 0;
    }
    int leftDepth = getMinDepth(node.left) + 1;
    int rightDepth = getMinDepth(node.right) + 1;
    return Math.min(leftDepth, rightDepth);
}
修改后 
public class Solution {
    public int run(TreeNode root) {
         if(root==null){
             return 0;
         }
        int left  = run(root.left);
        int right  = run(root.right);
        if(left*right >0){//判断，如果有一端是空，是返回数字大的非空一段，因为是求到叶子节点的距离
            return (left>right?right:left)+1;
        }else{
            return (left>right?left:right)+1;
        }
    }
}



编辑于 2020-04-30 01:57:57 回复(0)
哈啰内推排头兵头像 哈啰内推排头兵 
思路1：递归
若空树，则返回0
若左子树为空，则返回右子树最小深度+1
若右子树为空，则返回左子树最小深度+1
若左右子树均不为空，则返回左右子树较小者+1
import java.lang.Math;
public class Solution {
    public int run(TreeNode root) {
        //若空树，则返回0
        if(root == null) return 0;
        //若左子树为空，则返回右子树最小深度+1
        if(root.left==null) return run(root.right)+1;
        //若右子树为空，则返回左子树最小深度+1
        if(root.right==null) return run(root.left)+1;
        //若左右子树均不为空，则返回左右子树较小者+1
        return (Math.min(run(root.left),run(root.right))+1);
    }
}

思路2：层次遍历
若为空树，返回0
声明队列，头结点入队
声明深度记录变量depth
--------
若队列非空，每次处理一层的节点（即使用for循环来实现该处理）下一层节点进入队列。
判断条件：当出现节点左右子树均为空时，则此时的层数记为最短路径长。
        否则，左子树、右子树进队
--------
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int run(TreeNode root) {
        if(root == null) return 0;//若为空树，返回0
        if(root.left==null && root.right==null) return 1;
        //声明队列，声明深度记录变量
        Queue<TreeNode> queue = new LinkedList<>();
        //声明队列，头结点入队
        queue.offer(root);
        //声明深度记录变量depth
        int depth = 0;
        
        while(!queue.isEmpty()){
            int len = queue.size();
            depth++;
            //若队列非空，每次处理一层的节点（即使用for循环来实现该处理）下一层节点进入队列。
            for(int i=0;i<len;i++){
                TreeNode curNode = queue.poll();
                //判断条件：当出现节点左右子树均为空时，则此时的层数记为最短路径长。
                if(curNode.left==null && curNode.right==null) return depth;
                //左子树非空，左子树进队
                if(curNode.left != null) queue.offer(curNode.left);
                //右子树非空，右子树进队
                if(curNode.right != null) queue.offer(curNode.right);
            }
        }
        return 0;
    }
}

发表于 2020-04-22 22:05:03 回复(0)
黄_璜头像 黄_璜
非递归思路写法，简单易懂，进行二叉树的层数遍历，当找到第一个叶子节点是返回其深度。

class Solution {
public:
    int run(TreeNode *root) {
        if(root==nullptr)
        {
            return 0;
        }
        int num=1;
        TreeNode *last=root;  //本层的最后一个节点
        TreeNode *nlast=NULL; //下一层最后一个节点
        queue<TreeNode*> q;
        q.push(root);
        //结束条件为左右节点都为空节点
        while(!q.empty())
          {
            TreeNode *pi=q.front();
            q.pop();
            if(pi->left==NULL&&pi->right==NULL)//结束条件，第一个叶子节点
            {
                return num;
            }
            if(pi->left!=NULL)
            {
                q.push(pi->left);
                nlast=pi->left;
            }
            if(pi->right!=NULL)
            {
                q.push(pi->right);
                nlast=pi->right;
            }
            if(pi==last) //本层的节点数遍历到最后一个了，更新last
            {
                last=nlast;
                num++;
            }
          }
    }

};
发表于 2020-01-09 17:13:02 回复(0)
索悟头像 索悟 
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
        if(root==null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left != null && root.right != null)
            return min(run(root.left),run(root.right))+1;
        return max(run(root.left),run(root.right))+1;
        
    }
    public int min(int a,int b){
        return a > b ? b : a;
    }
    public int max(int a,int b){
        return a > b ? a : b;
    }
}
java递归解决，遇到空值返回0，遇到叶子节点返回1，遇到只有一个子节点的，则继续沿着子节点递归，直到遍历至叶子节点
发表于 2019-10-22 11:30:53 回复(0)
菜鸟四号头像 菜鸟四号

方法1：递归

思路：每个结点都有三种情况

1.不存在左右孩子，此时就找到了最小深度，返回即可
2.存在左孩子或存在右孩子
    2.1存在左孩子，需要查找右孩子的最大深度
    2.2存在右孩子，需要查找左孩子的最大深度
3.存在左孩子和右孩子，需要查找左孩子和右孩子之间的较小值

代码实现： 
public class Solution {
    public int run(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null) return 1;
        if(root.left==null || root.right==null) return Math.max(run(root.left),run(root.right))+1;
        return Math.min(run(root.left),run(root.right))+1;
    }

方法2：非递归

思路：层次遍历，找到第一个无左右孩子的结点
每次遍历并取出队列中的首位元素，并执行如下操作：
1.如果不存在左右孩子，此时找到了最小深度，返回即可
2.存在左孩子或存在右孩子
    2.1存在左孩子，需要将左孩子入队
    2.2存在右孩子，需要将右孩子入队
深度加1，然后重复上述步骤
代码如下： 
import java.util.*;
public class Solution {
    public int run(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int depth=1;
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node.left==null && node.right==null) return depth;
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            depth++;
        }
        return depth;
    }
}


发表于 2019-10-21 11:28:47 回复(0)
张佃鹏头像 张佃鹏

3年多没写 C++ 了，感觉好多语法都得网上查，要清楚一点，叶子几点是左右子树都为空的节点。

递归遍历，获取每个节点左右子树的最小深度 

class Solution {
public:
    int run(TreeNode *root) {
        if(root == NULL){
            return 0;
        }else if(root->left and root->right){
            return min(run(root->left), run(root->right)) + 1;
        }else if(root->left){
            return run(root->left) + 1;
        }else if(root->right){
            return run(root->right) + 1;
        }  
   }
};

层次遍历，从上往下一层一层的找，一旦找到就停止 

class Solution {
public:
    int run(TreeNode *root) {
        if(root == NULL){
            return 0;
        }
        queue<TreeNode *> q1;
        int level = 0;
        q1.push(root);
        while(q1.size() != 0){
            level++;
            queue<TreeNode *> q2;
            while(q1.size() != 0){
                TreeNode* node1 = q1.front();
                q1.pop();
                if(!node1->left and !node1->right){
                    return level;
                }else{
                    if(node1->left){
                        q2.push(node1->left);
                    }
                    if(node1->right){
                        q2.push(node1->right);
                    }
                }
            }
            q1 = q2;
        }
        return level;
   }
};
编辑于 2019-10-01 11:01:46 回复(0)
promethus头像 promethus 
// BFS，层序遍历,找到第一个叶子节点的层数
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            for(int i = 0; i < size; ++i)
            {
                TreeNode* tmp = que.front();
                if(tmp->left != NULL)
                    que.push(tmp->left);
                if(tmp->right != NULL)
                    que.push(tmp->right);
                que.pop();
                // 找到第一个叶子节点，返回
                if(tmp->left == NULL && tmp->right == NULL)
                    return depth;
            }
        }
        return -1;
    }
};

// 递归
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        return (min(left, right) ? min(left, right) : max(left, right)) + 1;
    }
};

发表于 2019-08-22 11:10:34 回复(0)
Java
锻心头像 锻心 

	public class Solution {
    public int run(TreeNode root) {





	      // 递归结束条件
        if(root == null){
            return 0;
        }





	      // 获取左子树的深度
        int lDepth = run(root.left);





	      // 获取右子树的深度
        int rDepth = run(root.right);





	





	      // 对没有孩子的结点进行判断
        if(lDepth + rDepth == 0){
            return 1;
        }





	      // 对只有一个孩子的结点进行判断
        if(lDepth * rDepth == 0){
            return lDepth + rDepth + 1;
        }





	      // 对左右子树深度进行最小值求取
        return Math.min(lDepth, rDepth) + 1;
    }
}
运用好递归思想和深入了解二叉树的原理就不是那么难。
发表于 2019-07-09 19:42:31 回复(0)
提交观点

问题信息

树
难度：
471条回答 69813浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的最小深度

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号