首页 > 试题广场 >

二叉树的最小深度

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

示例1

输入

{1,2,3,4,5}

输出

2

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
来个非递归的,思路是层序遍历,找到第一个左右结点都为null的情况,就返回
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public int run(TreeNode root) {
        if(root == null)
			return 0;
		if(root.left == null && root.right == null)
			return 1;
		
		int depth = 0;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()){
			int len = queue.size();
			depth++;
			for(int i = 0; i < len; i++){
				TreeNode cur = queue.poll();			
				if(cur.left == null && cur.right == null)
					return depth;
				if(cur.left != null)
					queue.offer(cur.left);
				if(cur.right != null)
					queue.offer(cur.right);
			}				
		}
		return 0;
    }
}

发表于 2017-05-22 19:39:02 回复(17)
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)
            return run(root.right)+1;
        if(root.right==null)
            return run(root.left)+1;
        return Math.min(run(root.left),run(root.right))+1;
    }
}

编辑于 2016-05-29 21:22:53 回复(3)
【java】同样是递归和非递归2种方法,了解一下
1.先来非递归:
思路:BFS标准解法,使用nextcount来记录下一层当前层还剩下的节点数,当前层数layer
1.入队标准:节点不为空,
1.1提前退出条件,当前节点是叶子节点,左右节点都是null,返回layer
1.2left或right不为空,入队一次下一层个数(next)+1
2.出队标准:无,出队一次,当前层(count--)减一
3.更新层数:当前层剩余个 count==0时
count = next;  //获取下一层个数
layer++;//遍历下一层,层数加1
next= 0;//复位
 public int run(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        int next = 0;//下一层个数
        int count = 1;//当前剩余个数
        int layer = 1;//当前层数
        q.offer(root);
        
        while(!q.isEmpty()) {
            TreeNode cur = q.poll();
            --count;//每弹出一个数,当前层减一
            if(cur.left == null && cur.right == null) return layer;
            if(cur.left != null) {
                q.offer(cur.left);
                ++next;//每加入一个数,当前层+1
            }
            if(cur.right != null) {
                q.offer(cur.right);
                ++next;
            }
            if(count == 0) {//当前层剩余个数结束时,说明已经遍历结束,进入下一层
                count = next;//获取下一层个数
                next = 0;//复位
                ++layer; //遍历下一层,层数加1    
            }
        }
        return layer;
    }
2.递归版本
递归:
1.出口:
0:root==null
2.递:left = run(root.left) //遍历左子树
right = run(root.right)//遍历右子树
3.归:
return         left + right + 1 : 左节点或者右节点为null,就不需要比较大小
min(left,right) + 1 : 最小的深度 + 当前的深度
 public int run(TreeNode root) {
        if(root == null) return 0;
        int left = run(root.left);
        int right = run(root.right);
        if(left == 0 || right == 0) 
            return left + right + 1;
        return Math.min(left, right) + 1;
    }

编辑于 2018-06-21 08:39:06 回复(3)
class Solution {
public:
    int run(TreeNode *root) {
        int ldeep;
        int rdeep;
        if(root==NULL)
            return 0;
        ldeep=run(root->left);
        rdeep=run(root->right);
        if (ldeep==NULL)
            return rdeep+1;
        if (rdeep==NULL)
            return ldeep+1;
        if(ldeep<rdeep)
            return ldeep+1;
        else
            return rdeep+1;
    }
};
本题要注意最小深度与最大深度的区别:对于最大深度,不需要考虑当前子树是否为单子树(即一侧子树深度为0)的情况,即最大深度一直等于左右子树的最大值;对于最小深度,需要考虑当前子树是否为单子树的情况,对于双子树,其最小深度为左右子树的最小值,对于单子树,其最小深度为左右深度的最大值(因为有一侧的子树为0)。
发表于 2016-11-14 21:40:18 回复(2)

C++ solution

class Solution {
public:
    int run(TreeNode *root) {
        if (root == NULL) { return 0; }
        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;
        } else { return 1; }
    }
};
发表于 2017-10-31 14:58:54 回复(7)
可以使用深度遍历,加上剪枝。一个类静态变量保存当前搜索到的最小深度,当访问到的节点深度超过这个值时剪枝,不再继续遍历,可以一定程度上改善深度优先搜索的性能。当然特殊的二叉树格式可能会导致跟不剪枝一样的结果。
class Solution {
public:
    static int depth;
    int run(TreeNode *root)
    {
        depth=1;
        if(root==NULL)
            return 0;
        if(root->left!=NULL)
            dfs(root->left, 1);
        if(root->right!=NULL)
            dfs(root->right, 1);
        return depth;
    }
    
    void dfs(TreeNode *r, int d)
    {
        d++;
        if(d>depth&&depth>1)
            return;
        if(r->left==NULL&&r->right==NULL&&(depth==1||d<depth))
        {
            depth=d;
            return;
        }
        if(r->left!=NULL)
            dfs(r->left, d);
        if(r->right!=NULL)
            dfs(r->right, d);
        return;
    }
};
int Solution::depth=1;

发表于 2017-08-08 16:26:07 回复(0)
递归
5种情况:空树;没有子树;只有左/右子树;有俩子树;
注意:结点 node.left
          指针 root->left
发表于 2017-04-11 20:42:10 回复(0)
//层次遍历 获取第一个叶子节点
    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)
三行代码搞定
public int run(TreeNode root) {
    if (root == null) return 0;
    int r = run(root.right), l = run(root.left);
    return r * l == 0 ? r + l + 1 : Math.min(r, l) + 1;
}



编辑于 2017-10-11 16:47:55 回复(0)

采用层次遍历,如果该层有叶节点,那么最短depth到此为止,如果没有,就遍历下一层

        if (root == null)   //是0
            return 0;
        //根不空,放入
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int depth = 1;  //根存在,设为1

        int cur = 0, last = 1; //cur开始指向当前层第一个节点,last指向下一层第一个
        while (cur < list.size()){
            last = list.size();    //last指向下一层第一个
            //访问当前层,看一看有没有叶子节点,如果有,那么最短路径就已经求出,否则路径长度加1,指向下一层
            while (cur < last){
                TreeNode curNode = list.get(cur);   //取当前节点
                if (curNode.left == null && curNode.right == null)
                    return depth;
                else {
                    if (curNode.left != null)
                        list.add(curNode.left);
                    if (curNode.right != null)
                        list.add(curNode.right);
                }

                cur++;  //cur指向下一个节点
            }
            //当前层没有叶子节点,depth + 1
            depth++;
        }

        return depth;
编辑于 2017-04-05 18:32:41 回复(3)
递归遍历左子树和右子树,返回最小的那个,然后加一 即为树的最小深度
class Solution {
public:
    int run(TreeNode *root) {
        if(root == NULL) 
            return 0;  
        int lmin = run(root->left);  
        int rmin = run(root->right);  
        
        if(lmin==0 && rmin == 0)  
            return 1;  
        if(lmin == 0)  
            lmin = INT_MAX;  
        if(rmin == 0)  
            rmin = INT_MAX;  
        
        return min(lmin, rmin)+1; 
    }
};

发表于 2016-03-09 12:32:13 回复(4)
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)
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)
 
第一种使用递归思想
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)
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)
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)

问题信息

难度:
471条回答 67671浏览

热门推荐

通过挑战的用户

查看代码