[Leetcode] Maximum and Minimum Depth of Binary Tre

boredream 发布于2019-08-14 12:30 / 717人阅读

摘要：递归法复杂度时间空间递归栈空间思路简单的递归。该递归的实质是深度优先搜索。这里我们还有改进的余地，就是用迭代加深的有限深度优先搜索。

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。基础条件是，当遇到空节点时，返回深度为0。该递归的实质是深度优先搜索。

代码

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) 递归栈空间

思路

当求最大深度时，我们只要在左右子树中取较大的就行了，然而最小深度时，如果左右子树中有一个为空会返回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;
    }
}

广度优先搜索 复杂度

时间 O(N) 空间 O(B)

思路

递归解法本质是深度优先搜索，但因为我们是求最小深度，并不一定要遍历完全部节点。如果我们用广度优先搜索，是可以在遇到第一个叶子节点时就终止并返回当前深度的。

代码

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;
    }
}

迭代加深有限深度优先搜索 复杂度

时间 O(N) 空间 O(D)

思路

英文名是Iterative Deepening Depth Limited Search.然而，广度优先搜索有一个致命缺陷就是，一旦分支变多，消耗空间就太大。这里我们还有改进的余地，就是用迭代加深的有限深度优先搜索。该算法每次迭代是一次有限深度优先搜索，如果本轮迭代没有发现目标（这题的目标是第一个叶子结点），则增加深度上限重新进行有限深度优先搜索。读者可能觉得这样会带来很多重复计算，但实际上经过数学证明后可以发现，该算法的时间复杂度和广度优先搜索是在一个数量级的，并没有太大的增加，而他的空间消耗仅仅是限制的深度。详情请翻阅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++;
            }
        }
    }
}

混合云私有云 Maximum Minimum Depth LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64524.html

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

摘要：解题思路用递归实现很简单，对于每个根节点，最大深度就等于左子树的最大深度和右子树的最大深度的较大值。解题思路本题的注意点在于如果某个根节点有一边的子树为空，那么它的深度就等于另一边不为空的子树的深度，其他的逻辑与上一题相同。 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 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

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