[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的相关教程结束。