111. 二叉樹的最小深度

題目：給定一個二叉樹，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明：葉子節點是指沒有子節點的節點。

方法1：深度優先搜索

原理：深度優先搜索（Depth First Search）是一種遍歷圖的算法，它從圖中的某個頂點出發，沿著一條路徑不斷向下探索，直到無法繼續深入為止，然后回溯到上一個頂點，繼續探索其他路徑，直到所有頂點都被訪問過為止，?所有的頂點都被壓入棧中。棧：先進后出。

思路：使用深度優先搜索，遍歷整棵樹，記錄最小的深度。對于每一個非葉子節點，分別計算其左右葉子結點的最小葉子結點深度。通過遞歸的方式解決該問題。但遞歸在運行時，值的變化很難把握。

   public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 最小深度
        int min_depth = Integer.MAX_VALUE;
        // 左子樹節點
        if(root.left != null){
            min_depth = Math.min(minDepth(root.left), min_depth);
        } 
        // 右子樹節點
        if(root.right != null){
            min_depth = Math.min(minDepth(root.right), min_depth);
        } 
        return min_depth + 1;
}

時間復雜度為O(N)，因為二叉樹中，每一個子節點都被訪問過。平均空間復雜度O(logN)。　　

方法2：廣度優先搜索

原理：廣度優先搜索（Breadth First Search）是一種遍歷圖的算法，它從圖中的某個頂點出發，沿著一條路徑不斷向下探索，直到無法繼續深入為止，然后回溯到上一個頂點，繼續探索其他路徑，直到所有頂點都被訪問過為止，?所有的頂點都被壓入隊列中。隊列：先進先出。

思路：使用廣度優先搜索，當我們找到一個葉子節點時，直接返回這個葉子節點的深度。廣度優先搜索的性質保證了最先搜索到的葉子節點的深度一定最小。

class QueueNode{
        // 定義屬性
        TreeNode node;
        int depth;
        // 構造函數
        public QueueNode(TreeNode node,int depth){
            this.node = node;
            this.depth = depth;
        }
    }
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<QueueNode> queue1 = new LinkedList<QueueNode>();
        queue1.offer(new QueueNode(root,1));// 先將第一個根節點放入隊列中
        while(!queue1.isEmpty()){
            // 彈出首個元素
            QueueNode nodedepth = queue1.poll();
            TreeNode node = nodedepth.node;
            int depth = nodedepth.depth;
            if (node.left == null && node.right == null) {
                // 最終的出口一定在這里
                return depth;
            }
            // 左子樹節點
            if(node.left != null){
                // 將節點放入隊列中 depth = depth + 1
                queue1.offer(new QueueNode(node.left,depth + 1));
            } 
            // 右子樹節點
            if(node.right != null){
                // 將節點放入隊列中 depth = depth + 1
                queue1.offer(new QueueNode(node.right,depth + 1));
            } 
        }
        return 0;
    }

?時間復雜度為O(N)，因為二叉樹中，每一個子節點都被訪問過。平均空間復雜度O(N)?！?/span>