[Leetcode] Maximum and Minimum Depth of Binary Tre

boredream 發(fā)布于2019-08-14 12:30 / 866人閱讀

摘要：遞歸法復(fù)雜度時(shí)間空間遞歸棧空間思路簡(jiǎn)單的遞歸。該遞歸的實(shí)質(zhì)是深度優(yōu)先搜索。這里我們還有改進(jìn)的余地，就是用迭代加深的有限深度優(yōu)先搜索。

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(H) 遞歸棧空間

思路

簡(jiǎn)單的遞歸。遞歸條件是，它的最大深度是它左子樹的最大深度和右子樹最大深度中較大的那個(gè)加1。基礎(chǔ)條件是，當(dāng)遇到空節(jié)點(diǎn)時(shí)，返回深度為0。該遞歸的實(shí)質(zhì)是深度優(yōu)先搜索。

代碼

public class Solution {

public int maxDepth(TreeNode root) {
    if(root == null){
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

}

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.

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(H) 遞歸棧空間

思路

當(dāng)求最大深度時(shí)，我們只要在左右子樹中取較大的就行了，然而最小深度時(shí)，如果左右子樹中有一個(gè)為空會(huì)返回0，這時(shí)我們是不能算做有效深度的。所以分成了三種情況，左子樹為空，右子樹為空，左右子樹都不為空。當(dāng)然，如果左右子樹都為空的話，就會(huì)返回1。

代碼

public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int depth = 0;
        if(root.left != null && root.right != null){
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            depth = Math.min(left, right);
        } else if (root.left != null){
            depth = minDepth(root.left);
        } else if (root.right != null){
            depth = minDepth(root.right);
        }
        return depth + 1;
    }
}

廣度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(N) 空間 O(B)

思路

遞歸解法本質(zhì)是深度優(yōu)先搜索，但因?yàn)槲覀兪乔笞钚∩疃龋⒉灰欢ㄒ闅v完全部節(jié)點(diǎn)。如果我們用廣度優(yōu)先搜索，是可以在遇到第一個(gè)葉子節(jié)點(diǎn)時(shí)就終止并返回當(dāng)前深度的。

代碼

public class Solution {
    public int minDepth(TreeNode root) {
        Queue queue = new LinkedList();
        if(root!=null) queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for(int i = 0; i < size; i++){
                TreeNode curr = queue.poll();
                if(curr.left == null && curr.right == null){
                    return depth;
                }
                if(curr.left != null) queue.offer(curr.left);
                if(curr.right != null) queue.offer(curr.right);
            }
        }
        return depth;
    }
}

迭代加深有限深度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(N) 空間 O(D)

思路

英文名是Iterative Deepening Depth Limited Search.然而，廣度優(yōu)先搜索有一個(gè)致命缺陷就是，一旦分支變多，消耗空間就太大。這里我們還有改進(jìn)的余地，就是用迭代加深的有限深度優(yōu)先搜索。該算法每次迭代是一次有限深度優(yōu)先搜索，如果本輪迭代沒有發(fā)現(xiàn)目標(biāo)（這題的目標(biāo)是第一個(gè)葉子結(jié)點(diǎn)），則增加深度上限重新進(jìn)行有限深度優(yōu)先搜索。讀者可能覺得這樣會(huì)帶來很多重復(fù)計(jì)算，但實(shí)際上經(jīng)過數(shù)學(xué)證明后可以發(fā)現(xiàn)，該算法的時(shí)間復(fù)雜度和廣度優(yōu)先搜索是在一個(gè)數(shù)量級(jí)的，并沒有太大的增加，而他的空間消耗僅僅是限制的深度。詳情請(qǐng)翻閱Artificial Intelligence : A Modern Approach。

代碼

public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        return iterativeDeepeningDFS(root);
    }
    private boolean depthLimitedSearch(TreeNode root,int depth){
        boolean left = false;
        boolean right = false;
        if(depth>0){
            if(root.left==null&&root.right==null){
                return true;
            }
            if(root.left!=null) {
                left = depthLimitedSearch(root.left, depth-1);
            }
            if(root.right!=null) {
                right = depthLimitedSearch(root.right, depth-1);
            }
            return left||right;
        } else {
            return false;
        }
    }
    private int iterativeDeepeningDFS(TreeNode root){
        int thisDepth = 1;
        boolean foundMin = false;
        while(true){
            foundMin = depthLimitedSearch(root,thisDepth);
            if(foundMin){
                return thisDepth;
            } else {
                thisDepth++;
            }
        }
    }
}