代码随想录算法训练营第十六天 | 二叉树的最大、最小深度、完全二叉树的节点个数

2次阅读
没有评论

104. 二叉树的最大深度

leetcode
文档题解
视频题解

二叉树节点的深度:该节点到树根的距离,从下到上。

二叉树节点的高度:该节点到叶子节点的最长距离,从上到下。

前序遍历可以求节点的深度,后序遍历可以求节点的高度。

二叉树的最大深度(高度)其实就是根节点的高度,因此可以使用后序遍历。

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

        int lh = maxDepth(root.left);
        int rh = maxDepth(root.right);

        // 以 root 为根的树的深度是左右子树中最大的深度 + 1
        return Integer.max(lh, rh) + 1;
    }
}

111. 二叉树的最小深度

leetcode
文档讲解
视频讲解

if (root == null) return 0;

        int ld = minDepth(root.left);
        int rd = minDepth(root.right);

        // 重点,二叉树的深度一定是要触及到叶子节点的
        // 如果只有右孩子,则最小深度要从右子树算起
        if (root.left == null && root.right != null) {return 1 + rd;}

        // 如果只有左孩子,则最小深度要从左子树算起
        if (root.right == null && root.left != null) {return 1 + ld;}

        return 1 + Integer.min(ld, rd);

222. 完全二叉树的节点个数

leetcode
文档题解
视频题解

遍历树,时间复杂度 O(n)。

// 后序遍历(递归)class Solution {public int countNodes(TreeNode root) {if (root == null) return 0;
        // 统计左右子树的节点数量,然后再加上根节点的数量
        int ls = countNodes(root.left);
        int rs = countNodes(root.right);
        return ls + rs + 1;
    }
}

// 层序遍历(迭代)class Solution {public int countNodes(TreeNode root) {if (root == null) return 0;
        int count = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {TreeNode node = q.poll();
            count++;
            if (node.left != null) {q.offer(node.left);
            }
            if (node.right != null) {q.offer(node.right);
            }
        }
        return count;
    }
}

题目强调了“完全二叉树”,可以使用以下解法。

完全二叉树的两种表现形式:满二叉树、普通完全二叉树(即最后一层没铺满)。

可以将完全二叉树看作是一些满二叉树 + 分支节点组成的,如下图:

代码随想录算法训练营第十六天 | 二叉树的最大、最小深度、完全二叉树的节点个数

满二叉树的节点数量可以用公式计算:2 ^ 树的高度 - 1。

该题还是可以通过后序遍历的方式计算节点数量,只不过遇到满二叉树时可以通过公式提高计算速度。

if (root == null) return 0;

        TreeNode l = root.left;
        TreeNode r = root.right;
        int ls = 0;
        int rs = 0;

        while (l != null) {
            l = l.left;
            ls++;
        }

        while (r != null) {
            r = r.right;
            rs++;
        }

        // 判断是否为“满二叉树”// 使用公式计算满二叉树的节点数量
        if (ls == rs) {return (2 << ls) - 1;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
正文完
 0
狐耳阿霖
版权声明:本站原创文章,由 狐耳阿霖 于2024-02-20发表,共计1533字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)