[Leetcode] Maximum and Minimum Depth of Binary Tre

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

摘要：遞歸法復雜度時間空間遞歸?？臻g思路簡單的遞歸。該遞歸的實質是深度優(yōu)先搜索。這里我們還有改進的余地，就是用迭代加深的有限深度優(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.

遞歸法 復雜度

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

思路

簡單的遞歸。遞歸條件是，它的最大深度是它左子樹的最大深度和右子樹最大深度中較大的那個加1?；A條件是，當遇到空節(jié)點時，返回深度為0。該遞歸的實質是深度優(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.

遞歸法 復雜度

時間 O(N) 空間 O(H) 遞歸?？臻g

思路

當求最大深度時，我們只要在左右子樹中取較大的就行了，然而最小深度時，如果左右子樹中有一個為空會返回0，這時我們是不能算做有效深度的。所以分成了三種情況，左子樹為空，右子樹為空，左右子樹都不為空。當然，如果左右子樹都為空的話，就會返回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)先搜索 復雜度

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

思路

遞歸解法本質是深度優(yōu)先搜索，但因為我們是求最小深度，并不一定要遍歷完全部節(jié)點。如果我們用廣度優(yōu)先搜索，是可以在遇到第一個葉子節(jié)點時就終止并返回當前深度的。

代碼

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)先搜索 復雜度

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

思路

英文名是Iterative Deepening Depth Limited Search.然而，廣度優(yōu)先搜索有一個致命缺陷就是，一旦分支變多，消耗空間就太大。這里我們還有改進的余地，就是用迭代加深的有限深度優(yōu)先搜索。該算法每次迭代是一次有限深度優(yōu)先搜索，如果本輪迭代沒有發(fā)現(xiàn)目標（這題的目標是第一個葉子結點），則增加深度上限重新進行有限深度優(yōu)先搜索。讀者可能覺得這樣會帶來很多重復計算，但實際上經過數(shù)學證明后可以發(fā)現(xiàn)，該算法的時間復雜度和廣度優(yōu)先搜索是在一個數(shù)量級的，并沒有太大的增加，而他的空間消耗僅僅是限制的深度。詳情請翻閱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++;
            }
        }
    }
}

云服務器 GPU云服務器 Maximum Minimum Depth LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/64524.html

[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解題思路用遞歸實現(xiàn)很簡單，對于每個根節(jié)點，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點在于如果某個根節(jié)點有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數(shù)據(jù)結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉樹最大深度

LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹的最深深度。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 ...

PiscesYE 2019-08-16 13:28 評論0 收藏0