Java 求解完全二叉树的节点个数

• • 一、题目
  • 二、递归法
  • 三、迭代法
  • 四、总结

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

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

该题求解二叉树的节点数目，和完全二叉树关系不大，可以看作求解二叉树的节点数，递归法和求解二叉树的最大深度类似

采用后序遍历，遍历左子树，遍历右子树

（1）确定递归参数及返回值

参数：二叉树节点，返回值：节点数目

（2）确定递归终止条件

当节点为空时，返回0

（3）确定递归逻辑

递归遍历左子树，递归遍历右子树

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //递归遍历左子树，右子树
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

层序遍历的思想：

import java.util.Deque;
import java.util.linkedList;

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //记录节点数量
        int res = 0;
        int size;
        TreeNode node;
        Deque deque = new linkedList<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            size = deque.size();
            while (size > 0) {
                node = deque.poll();
                res++;
                size--;
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
            }
        }
        return res;
    }
}

该题大同小异，注意分析，递归法，迭代法