完全二叉树的节点个数

题目描述

力扣链接🔗

完全二叉树的节点个数 - 图1

代码解析

以普通二叉树的思路来求

递归遍历

参考二叉树深度递归遍历的思想，可以使用二叉树递归遍历模板。

二叉树深度需要比较的是左右孩子的深度最大值，而此时求得是节点数，所以左右孩子 + 1（当前节点）即为此节点得节点数。

  1. /**
  2. * 递归法
  3. *
  4. * @param root
  5. * @return
  6. */
  7. public int countNodes(TreeNode root) {
  8.     return reverse(root);
  9. }
  11. public int reverse(TreeNode root) {
  12.     if (root == null) { // 当为空时，表示没有节点，返回0
  13.         return 0;
  14.     }
  15.     int leftNum = reverse(root.left);   // 计算左孩子的节点数
  16.     int rightNum = reverse(root.right);  // 计算右孩子的节点数
  17.     return leftNum + rightNum + 1;      // 左节点数 + 右节点数 + 中间节点
  18. }
  22. // 后序遍历简洁版（类似求深度时的求高度遍历）
  23. public int countNodes(TreeNode root) {
  24.     if (root == null) return 0;
  25.     return 1 + countNodes(root.left) + countNodes(root.right);
  26. }
  • 时间复杂度：完全二叉树的节点个数 - 图2#card=math&code=O%28n%29&id=ITk8w)
  • 空间复杂度：完全二叉树的节点个数 - 图3#card=math&code=O%28%5Clog%20n%29&id=bT26H)，算上了递归系统栈占用的空间

迭代遍历

层序迭代遍历模板修改即可。

  1. /**
  2.  * 层序遍历
  3.  * @param root
  4.  * @return
  5.  */
  6. public int countNodes(TreeNode root) {
  7.     if (root == null) {
  8.         return 0;
  9.     }
  11.     Queue<TreeNode> queue = new LinkedList<>();
  12.     queue.offer(root);
  13.     int num = 0;
  15.     while (!queue.isEmpty()) {
  16.         int len = queue.size();
  17.         while (len > 0) {
  18.             TreeNode node = queue.poll();
  19.             if (node.left != null) queue.offer(node.left);
  20.             if (node.right != null) queue.offer(node.right);
  21.             num++;  // 节点个数加一
  22.             len--;
  23.         }
  24.     }
  25.     return num;
  26. }
  • 时间复杂度：完全二叉树的节点个数 - 图4#card=math&code=O%28n%29&id=JFWO8)
  • 空间复杂度：完全二叉树的节点个数 - 图5#card=math&code=O%28n%29&id=AFR87)

完全二叉树思想

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树的节点个数 - 图6

完全二叉树的节点个数 - 图7

如果整个树不是满二叉树，则递归整个树来求节点数，如果为满二叉树，使用满二叉树得公式求节点即可。

  1. /**
  2.  * 完全二叉树的性质
  3.  *
  4.  * @param root
  5.  * @return
  6.  */
  7. public int countNodes(TreeNode root) {
  8.     if (root == null) {
  9.         return 0;
  10.     }
  12.     TreeNode leftNode = root.left;
  13.     TreeNode rightNode = root.right;
  14.     int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
  16.     // 求左孩子的深度
  17.     while (leftNode != null) {
  18.         leftNode = leftNode.left;
  19.         leftDepth++;
  20.     }
  22.     // 求右孩子的深度
  23.     while (rightNode != null) {
  24.         rightNode = rightNode.right;
  25.         rightDepth++;
  26.     }
  28.     if (leftDepth == rightDepth) {      // 此时为满二叉树
  29.         return (2 << leftDepth) - 1;    // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
  30.     }
  32.     // 不为满二叉树则继续递归，注意加上自身节点
  33.     return countNodes(root.left) + countNodes(root.right) + 1;
  34. }
  • 时间复杂度：完全二叉树的节点个数 - 图8#card=math&code=O%28%5Clog%20n%20%C3%97%20%5Clog%20n%29&id=hkNdP)
  • 空间复杂度：完全二叉树的节点个数 - 图9#card=math&code=O%28%5Clog%20n%29&id=sJLpF)
  1. // 求左孩子的深度
  2. while (leftNode != null) {
  3.     leftNode = leftNode.left;
  4.     leftDepth++;
  5. }
  7. // 求右孩子的深度
  8. while (rightNode != null) {
  9.     rightNode = rightNode.right;
  10.     rightDepth++;
  11. }

这段代码就是来判断是否为满二叉树，最左边深度和最右边的深度进行比较，根据满二叉树的性质。