难度：中等
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
思路本文总共实现了三种方法
直接递归版本,没有利用到完全二叉树的特性迭代版本,没有利用到完全二叉树的特性递归版本,利用完全二叉树的特性进行计算 利用完全二叉树的特性进行计算的递归版本
对于完全二叉树中的一个节点，如果它的左子树的深度等于右子树的深度，那么该节点是一颗完全二叉树，可以使用公式 n u m = 2 depth − 1 num = 2^{text{depth}}-1 num=2depth−1直接计算该子树的节点个数，可以减少一部分的递归时间
public int countNodes(TreeNode root) { if (root == null) { return 0; } int leftDepth = 1; int rightDepth = 1; TreeNode leftNode = root.left; TreeNode rightNode = root.right; while (leftNode != null) { leftDepth++; leftNode = leftNode.left; } while (rightNode != null) { rightDepth++; rightNode = rightNode.right; } if (leftDepth == rightDepth) { return (int) Math.pow(2, leftDepth) - 1; } return countNodes(root.left) + countNodes(root.right) + 1;}
直接递归版本public int countNodes(TreeNode root) { if (root == null) { return 0; } return countNodes(root.left) + countNodes(root.right) + 1;}
迭代版本public int countNodes(TreeNode root) { if (root == null) { return 0; } int nodeNum = 0; Deque deque = new linkedList<>(); deque.addLast(root); while (!deque.isEmpty()) { nodeNum++; TreeNode node = deque.removeFirst(); if (node.left != null) { deque.addLast(node.left); } if (node.right != null) { deque.addLast(node.right); } } return nodeNum;}