C/C++教程

[Leetcode 111]二叉树的最短深度 BFS/DFS

本文主要是介绍[Leetcode 111]二叉树的最短深度 BFS/DFS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

给定二叉树,求最短路径包含的节点个数

https://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.

Note: A leaf is a node with no children.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2
最短路径3-9,节点2个

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

思路

BFS比DFS合适

类似题:N叉树最大深度:https://www.cnblogs.com/inku/p/15642874.html

比如二叉树左边500右边1个节点

dfs先遍历完500个节点,再遍历1节点

bfs广度优先,左右俩边只要找到left和right同时为空的节点就返回

 

代码

DFS

 

    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        
        if (root.left == null && root.right == null)
            return 1;
 
        if (root.left == null)
            return minDepth(root.right) + 1;//left为空,走right
 
        if (root.right == null)
            return minDepth(root.left) + 1;//right为空,走left
 
        return 1+Math.min(minDepth(root.left), minDepth(root.right));
        //返回dfs后,左右中更小的,+1(root自身节点)
    }

最大深度:https://www.cnblogs.com/inku/p/9854535.html

 

 

BFS

其实就是层次遍历

左右节点为空时就返回的限制,成了min

 

    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        int ans=1;
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++) {
                TreeNode cur=q.remove();
                if (cur.left==null&&cur.right==null)
                    return ans;
                if(cur.left!=null)
                    q.offer(cur.left);
                if(cur.right!=null)
                    q.offer(cur.right);
            }
            ans++;
        }
        return ans;
    }

 

这篇关于[Leetcode 111]二叉树的最短深度 BFS/DFS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!