1. Toy模板网首页
  2. > Toy博客

【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

9月前 作者：苹果就叫不呐呐 分类：Toy博客 阅读(52) 违法举报

这篇具有很好参考价值的文章主要介绍了【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树节点的深度：
指从根节点到该节点的最长简单路径边的条数或者节点数
（取决于深度从0开始还是从1开始）
二叉树节点的高度：
指从该节点到叶子节点的最长简单路径边的条数后者节点数
（取决于高度从0开始还是从1开始）

【前序求的是深度，后序求的是高度】

---------------🎈🎈题目链接🎈🎈-------------------

Leetcode 104 二叉树的最大深度

解法1 深度优先 递归法 后序：左右中

即先求左子树高度，再求右子树高度，再取最大返回给根节点
返回最大深度也就是求根节点的高度

时间复杂度O(N)
空间复杂度O(N)文章来源地址https://www.toymoban.com/news/detail-826531.html

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // 返回最大深度也就是求根节点的高度
        // 采用深度优先 递归法 后序：左右中 即先求左子树高度，再求右子树高度，再取最大返回给根节点
        if(root == null) return 0;
        // 左
        int leftdepth = maxDepth(root.left);
        // 右
        int rightdepth = maxDepth(root.right);
        // 中
        return 1 + Math.max(leftdepth,rightdepth);
    }
}

解法2 广度优先：层序遍历

时间复杂度O(N)
空间复杂度O(N)


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // 层序遍历
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return 0;
        myqueue.add(root);
        int result = 0;
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
            }
            result +=1;
        }
        return result;

    }
}

Leetcode 111 二叉树的最小深度

---------------🎈🎈题目链接🎈🎈-------------------

解法1 深度优先：递归 后序遍历 左右中

这里要特别注意⭐️
最小深度—— 根节点到叶子节点的长度【左右孩子都为null的才是叶子结点】
/1.如果左子树为空，右子树不为空，最小深度是 1 + 右子树的深度。
/2.如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
/3.如果左右子树都不为空，返回左右子树深度最小值 + 1 。

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        // 深度优先遍历 递归 后序遍历 左右中
        // 最小深度—— 根节点到叶子节点的长度【左右孩子都为null的才是叶子结点】
        // 1.如果左子树为空，右子树不为空，最小深度是 1 + 右子树的深度。
        // 2.如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
        // 3.如果左右子树都不为空，返回左右子树深度最小值 + 1 。

        if(root == null) return 0; //递归终止条件，遇到null返回0，表示当前的节点的高度为0
        int leftdepth = minDepth(root.left); // 左
        int rightdepth = minDepth(root.right); // 右
        if(root.left == null){return 1+rightdepth;}
        else if(root.right == null){return 1+leftdepth;}
        else{
            return 1+Math.min(leftdepth,rightdepth);
        }
        
    }
    
}

解法2 广度优先：层序遍历

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        // 层序遍历
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return 0;
        myqueue.add(root);
        int result = 0;
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
                if(temp.left == null && temp.right==null){
                    return result+1;
                }
            }
            result +=1;
        }
        return result;

    }
}

Leetcode 110 平衡二叉树

【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树,Leetcode,深度优先,宽度优先,leetcode,数据结构,java,算法,职场和发展

解法1 深度优先，求高度则用后序遍历：不断将左右子树的高度返回给根节点

1 明确递归函数的参数和返回值
参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度。
2 明确终止条件
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
3 明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        int height = getHeight(root);
        if(height != -1) return true;
        else return false;

    }
    public int getHeight(TreeNode root){ // 参数和返回值
        if(root == null) return 0;  // 明确终止条件 递归的过程中遇到空节点终止，返回0，表示当前节点为根节点的树高度为0
        int leftheight = getHeight(root.left); // left
        if(leftheight == -1){
            return -1;
        }
        int rightheight = getHeight(root.right); // right
        if(rightheight == -1){
            return -1;
        }
        if(Math.abs(leftheight-rightheight) >1) return -1;  // root
        else{return Math.max(leftheight,rightheight)+1;}



    }
}

到了这里，关于【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包