LeetCode中的Maximum Depth of Binary Tree和Minimum Depth of Binary Tree的比較

首先

樹的題目一般可以使用遞歸來解決問題，而且遞歸的問題實(shí)在不能太關(guān)注于細(xì)節(jié)，應(yīng)該這樣將樹看成是一個(gè)由根節(jié)點(diǎn)，左子樹和右子樹組成的一樣?xùn)|西。

Maximum

第一題的思路應(yīng)該是這樣的，要算出來所有一個(gè)二叉樹的深度。什么是深度？其實(shí)直觀地看一個(gè)樹就是看這棵樹有多少層，這棵樹的深度就是多少。

那么如何算出來一個(gè)樹的深度呢？利用上面對一棵二叉樹的定義，可以這樣理解，左子樹和右子樹的深度中，選擇大的那一個(gè)，然后加上1,也就是根的層樹就行了。

但是，別忘了，這個(gè)思考的前提是樹不為null，當(dāng)樹為null的時(shí)候，沒有根，也沒有左子樹，也沒有右子樹，就當(dāng)然不能這樣算了。所以再劃分出來一種情況就是當(dāng)root為null的時(shí)候，返回的是0。

貼代碼：

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

Minimum

同理，第二道題目，最普遍的一種情況是左右子樹都存在的情況，這時(shí)候最小值是左，右子樹中取小的那一個(gè)深度，然后加上根就行了。

但是，這個(gè)考慮的時(shí)候，要考慮到除了根為空的時(shí)候，這一種特殊情況之外。還要考慮的是，當(dāng)左子樹為空的時(shí)候，上面那種最普遍的算法是不成立的，還按照上面那個(gè)來的話，會(huì)直接按空的子樹來算出來最短的深度，注意對比一下最大深度，這中特殊情況下，普通的算法也是可以算的。那么就要分別考慮左右子樹分別為空的情況了。

那么，左右子樹都為空的情況呢？需不需要另外考慮。其實(shí)是不需要的，因?yàn)槿绻笞訕錇榭蘸螅易訕湟彩菫榭?，那么返回的還是0,其實(shí)還是一個(gè)正確的答案。但是如果，單列出來，其實(shí)也是沒有是問題的。

下面貼出代碼：

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

還有一點(diǎn)提醒就是，要把最根本，或者這個(gè)情況成立的情況，其他情況不成立的情況，最先考慮，比如所root為null的情況。（有點(diǎn)語無倫次，不理解也沒有關(guān)系，反正我能懂吧？2333）。