SOURCE

// 思路
// 递归实现
// 在递归遍历二叉树的基础上 将中间节点 记为1 逐层返回中间节点 加 左右子树节点数
// 迭代实现
// 累加 每层 节点数
// 满二叉树特性实现
// 满二叉树节点数 可以用公式 2^深度 - 1 计算得到
// 可以通过判断子树左右两边层级是否相等 判断是否为满二叉树
// 不是满二叉树的则递归像左右子树遍历 并累加中间节点数
// 每递归一层 判断当前子树是否为满二叉树 是则根据公式直接返回当前子树节点数
// 注 叶子节点也是满二叉树
// 完全二叉树特性实现的优点在于 二叉树越大
// 这种实现方式时间上的优势越明显 因为不用遍历满二叉树中间部分的节点

class Node {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

let n1 = new Node(1, null, null);
let n2 = new Node(2, null, null);
let n4 = new Node(4, n1, n2);
let n6 = new Node(6, null, null);
let root = new Node(5, n4, n6);

// 递归实现 例 前序遍历
function fn1(node) {
    // 递归出口 递归到末端向上返回
    if (node == null) return 0
    // 单层递归逻辑
    let 左子树节点个数 = fn1(node.left)
    let 右子树节点个数 = fn1(node.right)
    let 中间节点个数 = 1
    return 左子树节点个数 + 右子树节点个数 + 中间节点个数
}

// 验证
console.log('递归实现', fn1(root)) // 5

// 层序遍历 迭代 实现
function fn2(root) {
    let result = 0
    let queue = [] // 辅助队列
    // 初始值 将根节点装入队列
    queue.push(root)
    while (queue.length) {
        // 记录初始队列
        let size = queue.length
        // 累加本层节点数
        result += size
        while (size--) {
            let node = queue.shift()
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return result
}

// 验证
console.log('迭代实现', fn2(root)) // 5

// 利用完全二叉树性质
function fn3(node) {
    if (node === null) {
        // 递归出口 空节点返回节点数0
        return 0
    }
    // 计数
    let 左节点数 = 0
    let 右节点数 = 0
    // 设置迭代指针
    let left = node.left
    // 有子节点计数+1
    while (left) {
        左节点数++
        // 向左遍历
        left = left.left
    }
    let right = node.right
    while (right) {
        右节点数++
        // 向右遍历
        right = right.right
    }
    // 之所以向左右遍历 是因为满二叉树特性 左右两边子节点铺满
    // 就可以用 2^深度 - 1 求得满二叉树节点个数
    if (左节点数 === 右节点数) {
        // 递归出口2 当前子树是满二叉树的情况
        // 左边 等于 右边 说明 是满二叉树 用公式计算当前满二叉树节点数
        // 注意 子树深度 + 1才是从当前节点开始的深度
        return Math.pow(2, 左节点数 + 1) - 1
    }
    // 当前子树不是满二叉树 则递归遍历左右子树 并加上中间节点数
    return fn3(node.left) + fn3(node.right) + 1
}

// 验证
console.log('利用满二叉树特性', fn3(root)) // 5