leetcode刷题：二叉树10（完全二叉树的节点个数）

力扣题目链接

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

示例 1：

• 输入：root = [1,2,3,4,5,6]
• 输出：6

示例 2：

• 输入：root = []
• 输出：0

示例 3：

• 输入：root = [1]
• 输出：1

提示：

• 树中节点的数目范围是[0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• 题目数据保证输入的树是 完全二叉树

直接层序遍历查，不失为一种快乐的方法。

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.Deque;


public class CountNodes {
    public int countNodes(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        Deque deque = new ArrayDeque();
        deque.offer(root);
        int sum = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size > 0) {
                root = deque.pop();
                sum++;
                if (root.left != null) {
                    deque.offer(root.left);
                }
                if (root.right != null) {
                    deque.offer(root.right);
                }
                size--;
            }
        }
        return sum;
    }
}

按照满二叉树的性质，节点数 = 前n-1层节点数 + 最后一层节点数
前n-1层节点数 = 2^(n-1) -1

    
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (leftDepth == rightDepth) {
            //如果深度相等，则左边为满二叉树
            // leftDepth是从当前子树的头结点开始计算深度，不是两棵树的根结点
            // ( 2 ^ leftDepth - 1 ) + 1   1为两棵树的根结点
            return ((1 << leftDepth) - 1) + 1 + countNodes(root.right);
        } else {
            //右子树为满二叉树
            return ((1 << rightDepth) - 1) + 1 + countNodes(root.left);
        }
    }

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