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

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

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

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

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

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

1. 根据完全二叉树的规律，如果左右子树的高度的相等，那么则左子树就是一个满二叉树，如果左右子树的高度的不相等，那么则右子树就是一个满二叉树。

2. 根据满二叉树的规律，满二叉树的节点数等于2^heigth - 1。

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

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

最后

以上就是雪白小鸭子为你收集整理的LeetCode Java刷题笔记—222. 完全二叉树的节点个数的全部内容，希望文章能够帮你解决LeetCode Java刷题笔记—222. 完全二叉树的节点个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。