LeetCode Java刷题笔记—222. 完全二叉树的节点个数

62 阅读 0 评论 41 点赞

我是靠谱客的博主雪白小鸭子，这篇文章主要介绍LeetCode Java刷题笔记—222. 完全二叉树的节点个数，现在分享给大家，希望可以做个参考。

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

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

中等难度。最简单同时比较好理解的方法就是递归的方式遍历：

复制代码

1
2
3
4
5
public int countNodes(TreeNode root) {
    //以当前节点为根节点的树节点个数 = 以左子节点为根节点的树节点个数为 + 以右子节点为根节点的树节点个数为 + 当前节点个数1
    return root == null ? 0 : countNodes(root.left) + countNodes(root.right) + 1;
}

但是这道题求完全二叉树的节点个数，那么我们有更好的方法，那就是根据规律计算节点数来减少遍历次数：

根据完全二叉树的规律，如果左右子树的高度的相等，那么则左子树就是一个满二叉树，如果左右子树的高度的不相等，那么则右子树就是一个满二叉树。
根据满二叉树的规律，满二叉树的节点数等于2^heigth - 1。

那么，下面的优化解法就更好理解了。注意这里计算的时候，使用的是1 << left，这样可以包含父节点计数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    //求左子树高度
    int left = getDepth(root.left);
    //求右子树高度
    int right = getDepth(root.right);
    //如果左右子树的高度的相等，那么则左子树就是一个满二叉树.
    //如果左右子树的高度的不等，那么则右子树就是一个满二叉树,或者null。
    return left == right ? (1 << left) + countNodes(root.right) : (1 << right) + countNodes(root.left);
}

int getDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        depth++;
        node = node.left;
    }
    return depth;
}