首页 > 试题广场 >

二叉树的最小深度

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

示例1

输入

{1,2,3,4,5}

输出

2

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
可以使用深度遍历,加上剪枝。一个类静态变量保存当前搜索到的最小深度,当访问到的节点深度超过这个值时剪枝,不再继续遍历,可以一定程度上改善深度优先搜索的性能。当然特殊的二叉树格式可能会导致跟不剪枝一样的结果。
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)
//层次遍历 获取第一个叶子节点
    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)
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)
        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)
这道题和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)