首页 > 试题广场 > minimum-depth-of-binary-tree
[编程题]minimum-depth-of-binary-tree
  • 热度指数:152379 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
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.
思路:
递归,若为空树返回0;
若左子树为空,则返回右子树的最小深度+1;(加1是因为要加上根这一层,下同)
若右子树为空,则返回左子树的最小深度+1;
若左右子树均不为空,则取左、右子树最小深度的较小值,+1;
参考代码:
class Solution {
public:
    int run(TreeNode *root) 
    {
        if(root == nullptr) return 0;
        if(root->left == nullptr) // 若左子树为空,则返回右子树的最小深度+1
        {
            return run(root->right)+1;
        }
        if(root->right == nullptr) // 若右子树为空,则返回左子树的最小深度+1
        {
            return run(root->left)+1;
        }
        // 左右子树都不为空时,取较小值
        int leftDepth = run(root->left);
        int rightDepth = run(root->right);
        return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
    }
};

发表于 2016-10-21 20:06:36 回复(12)
来个非递归的,思路是层序遍历,找到第一个左右结点都为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 回复(15)
class Solution {
public:
    typedef TreeNode* tree;
    int run(TreeNode *root) {
        //采用广度优先搜索,或者层序遍历,找到的第一个叶节点的深度即是最浅。
      if(! root) return 0;
      queue<tree> qu;
      tree last,now;
      int level,size;
      last = now = root;
      level = 1;qu.push(root);
      while(qu.size()){
        now = qu.front();
        qu.pop();
        size = qu.size();
        if(now->left)qu.push(now->left);
        if(now->right)qu.push(now->right);
        if(qu.size()-size == 0)break;
        if(last == now){
          level++;
          if(qu.size())last = qu.back();
        }
      }
      return level;
    }
};
看了很多答案都是用的深度优先遍历,我觉得这个题用层序更效率更高,因为它不需要去遍历所有的节点,一旦找到一个叶节点,它肯定是最短的。
发表于 2016-12-13 21:47:58 回复(20)
class Solution {
public:
    int run(TreeNode *root) {
        if(!root)
            return 0;
        int l = run(root->left);
        int r = run(root->right);
        if(l==0 || r==0)
            return 1+l+r;
        return 1+min(l,r);
    }
};

发表于 2016-07-28 11:08:09 回复(18)

使用递归

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;
    }
}

不使用递归

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;
        }
        Queue queue = new LinkedList();
        queue.add(root);
        int level = 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 level;
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            level++;
        }
        return level;
    }
}

总结

二叉树操作主要还是利用尾递归或者循环遍历这两种思路,进而涉及DFS(主要利用递归或者栈实现)或者BFS(主要利用队列实现)。剩下的只需要按照这些思路即可。

编辑于 2019-12-02 16:23:23 回复(0)
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 回复(2)
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)
class Solution {
public:
    int run(TreeNode *root) {
        if(root ==NULL) 
            return 0;
        int l = run(root->left);
        int r = run(root->right);
        if(l==0 || r==0)
            return l+r+1;
        return min(l, r) + 1;
    }
};

发表于 2017-09-23 13:15:12 回复(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)
三行代码搞定
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)
没错,就是找一个叶子结点
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)

采用层次遍历,如果该层有叶节点,那么最短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 回复(2)
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)
递归遍历左子树和右子树,返回最小的那个,然后加一 即为树的最小深度
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)
非递归思路写法,简单易懂,进行二叉树的层数遍历,当找到第一个叶子节点是返回其深度。

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)