二叉树的深度和高度问题(算法村第八关白银挑战)

发布时间:2024年01月11日

二叉树的最大深度

104. 二叉树的最大深度 - 力扣(LeetCode)

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

img
输入:root = [3,9,20,null,null,15,7]
输出:3 

提示:

  • 树中节点的数量在 [0, 104] 区间内。

递归

对于根节点,它到叶结点的最大深度 = 1 + max(左节点的最大深度,右节点的最大深度)。所以,我们只需递归地求当前结点到叶结点的最大深度即可

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

层序遍历

最大深度也即二叉树的层数,所以我们可以采用层序遍历的方法,每遍历完一层就记录二叉树的层数。

public int maxDepth(TreeNode root)
{
    if (root == null)
        return 0;

    int maxDepth = 0;
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty())
    {
        //当前层的结点个数
        int size = queue.size();

        for (int i = 0; i < size; i++)
        {
            TreeNode curNode = queue.poll();

            if (curNode.left != null)
                queue.offer(curNode.left);
            if (curNode.right != null)
                queue.offer(curNode.right);
        }

        maxDepth++; //当前层遍历完毕,总层数+1
    }

    return maxDepth;
}

N叉树的最大深度

559. N 叉树的最大深度 - 力扣(LeetCode)

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

示例 1:

img
输入:root = [1,null,3,2,4,null,5,6]
输出:3

示例 2:

img
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:5

提示:

  • 树的深度不会超过 1000
  • 树的节点数目位于 [0, 104] 之间。

递归

public int maxDepth(Node root)
{
    if (root == null)
        return 0;

    //没有分支即返回1,表示该结点的最大深度为1。
    //这一步很有必要,因为Collections.max()的形参集合不为空
    if (root.children.isEmpty())
        return 1;

    //存储各分支深度的列表
    ArrayList<Integer> depths = new ArrayList<>();

    for (Node node : root.children)
        depths.add(maxDepth(node));

    //返回该根结点的最大深度
    return 1 + Collections.max(depths);
}

层序遍历

public int maxDepth(Node root)
{
    if (root == null)
        return 0;

    int maxDepth = 0;
    ArrayDeque<Node> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty())
    {
        //当前层的结点个数
        int size = queue.size();


        for (int i = 0; i < size; i++)
        {
            Node curNode = queue.poll();

            for(Node child : curNode.children)
                if (child != null)
                    queue.offer(child);
        }

        maxDepth++; //当前层遍历完毕,总层数+1
    }

    return maxDepth;
}

平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode)

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

img
输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000]

求最大深度的过程中判断一下即可

public boolean isBalanced(TreeNode root)
{
    //假设它是平衡二叉树,找找看有没有反例(只有反例才能一直保存)
    boolean[] isBalanced = {true};
    maxDepth(root, isBalanced);

    return isBalanced[0];
}

public int maxDepth(TreeNode root, boolean[] isBalanced)
{
    if (root == null)
        return 0;

    int leftDepth = maxDepth(root.left, isBalanced);
    int rightDepth = maxDepth(root.right, isBalanced);

    if(Math.abs(leftDepth - rightDepth) > 1)
        isBalanced[0] = false;

    return 1 + Math.max(leftDepth, rightDepth);
}

二叉树的最小深度

111. 二叉树的最小深度 - 力扣(LeetCode)

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明:**叶子节点是指没有子节点的节点。

示例 1:

img
输入:root = [3,9,20,null,null,15,7]
输出:2

提示:

  • 树中节点数的范围在 [0, 105]

递归

在这里插入图片描述

public int minDepth(TreeNode root)
{
    if (root == null)
        return 0;

    //找到叶子结点
    if (root.left == null && root.right == null)
        return 1;

    //分支的最小深度
    int min_Depth = Integer.MAX_VALUE;

    //递归求出左分支的最小深度
    if (root.left != null)
        min_Depth = Math.min(min_Depth, minDepth(root.left));

    //递归求出右分支的最小深度,并与左分支比较,得出从该节点的孩子出发,到最近的叶节点的最小深度
    if (root.right != null)
        min_Depth = Math.min(min_Depth, minDepth(root.right));

    //返回该结点的最小深度
    return 1 + min_Depth;
}

层序遍历

public int maxDepth(TreeNode root)
{
    if (root == null)
        return 0;

    int minDepth = 0;
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty())
    {
        //当前层的结点个数
        int size = queue.size();

        minDepth++; //深度+1

        for (int i = 0; i < size; i++)
        {
            TreeNode curNode = queue.poll();

            //找到一个叶子结点就润
            if (curNode.left == null && curNode.right == null)
                return minDepth;

            if (curNode.left != null)
                queue.offer(curNode.left);
            if (curNode.right != null)
                queue.offer(curNode.right);
        }
    }

    return minDepth;
}
文章来源:https://blog.csdn.net/cjj2543107638/article/details/135520643
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。