image

題目

給定一個二叉樹，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

image

解題思路

之前有一道二叉樹的最大深度的題目比較類似，那道題是使用遞歸取左右子樹的深度取最大值。

遞歸解法

那這道題就是相反：取左右子樹深度的最小值，通過遞歸的過程。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left) + 1;
        int right = minDepth(root.right) + 1;
        return Math.min(left,right);
}

什么？
這樣不對，[2,1]不能通過。應(yīng)該輸出2，但是上面的代碼輸出了1。
再閱讀題目，原來它的要求是到葉子節(jié)點的深度，如果只有跟節(jié)點是不算作深度的，我們需要怎么改的，大家可以想一想

思考時間

我們可以判斷如果沒有左右子樹，就以其他的子樹的深度為準(zhǔn)。

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    //以右子樹的高度為準(zhǔn)
    if (root.left == null && root.right != null) {
        return 1 + minDepth(root.right);
    }
    //以左子樹的高度為準(zhǔn)
    if (root.right == null && root.left != null) {
        return 1 + minDepth(root.left);
    }

    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

迭代解法

這道題也可以使用迭代求解，利用層序遍歷記錄層數(shù)，到達葉子節(jié)點的時候，判斷得到一個最小的節(jié)點即可，自己寫下代碼把。