[leetcode]111.Minimum Depth of Binary Tree

左手的ㄟ右手 2022-08-22 14:29 8阅读 0赞

### 111. 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.

题目链接：[111. Minimum Depth of Binary Tree][]

这道题可以用递归或循环解决。下面给出两种方法的代码。  
对于循环方法来说，我们用BFS解决这道题并不用遍历整个树，而是当遇到第一个叶节点时就可以停止了。因为BFS广度优先遍历是从根开始向远的地方遍历的。那么遇到的第一个叶节点的深度显然也就是我们需要的最小深度。】  
具体分析请看代码中的注释。

其中iterative method的时间复杂度为O(2n\-1),空间复杂度为O(2n−1)，n为二叉树深度。  
recursive method的时间复杂度为（复习一下CRLS再算。）

/**
     * Definition for a binary tree node.
     * public class TreeNode {
        
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        /*
        iterative method
        */
        public int minDepth(TreeNode root){
            if (root == null){
                return 0;
            }
            //BFS
            //by BFS, we only need to consider about the first leaf node we encountered. Based on the mechanism of BFS, the first leaf node we encountered is the least deep leaf node in the tree. So we end the search as soon as we reach this leaf node. 
            Queue<TreeNode> nodes = new LinkedList<>();
            int depth = 0;
            nodes.offer(root);
            while (!nodes.isEmpty()){
                //this size is the current number of nodes in the queue. 
                //it makes use of the feature that at the begining of every iteration, only tree nodes of the same depth are stored in the tree. So we need to iterate "size" times in the later for loop to poll out all the nodes of the given depth while only increase depth for 1. 
                int size = nodes.size(); 
                ++depth;
                for (int i = 0; i < size; i ++){
                    TreeNode current = nodes.poll();
                    if (current.left == null & current.right == null){
                        //if current node is a leaf node, we end the BFS, cause this is the minimun depth we need. 
                        return depth;
                    }
                    if (current.left != null){
                        nodes.offer(current.left);
                    }
                    if (current.right != null){
                        nodes.offer(current.right);
                    }
                }
    
            }
    
            return depth;
        }
    
        /*
        recursive method
        */
        public int minDepth(TreeNode root) {
            if (root == null){
                return 0;
            }
            if (root.left != null && root.right != null){
                //if the current root we are considering have both left and right child, then we will choose the one with the smaller depth. 
                return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
            }
            else{
                //if the current root we are considering have only 1 child or no child
                //1 child: we choose the one with bigger depth, cause we are considering the leaf node, so if there is only one child, we need to go deeper on that node.
                //no child, no matter which child we choose, the result is the same, it will return 0 + 1.
                return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
            }
        }
    }

[111. Minimum Depth of Binary Tree]: https://leetcode.com/problems/minimum-depth-of-binary-tree/