[leetcode]111.Minimum Depth of Binary Tree

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