SOURCE

// 思路
// 二叉树性质有点像单链表 只能通过父节点 找到 子节点 而不能反向找父节点
// 因此当前节点无法判断自身是否为左叶子 必须通过 父节点 才能判断 并采集

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 fn(node) {
    // 因为只计算左叶子节点 因此要先求左右子树的结果 这种情况就适用 后序遍历
    let 左子树累计值 = 0
    // 虽然本例代码不算简洁 但是通过父节点过滤掉了 空节点 和 不必要节点 的递归 性能要更好
    if (node.left) {
        // 有左孩子
        if (node.left.left == null && node.left.right == null) {
            // 左孩子为叶子节点 则记录值
            左子树累计值 = node.left.value
        } else {
            // 不是叶子节点 则继续递归
            左子树累计值 = fn(node.left)
        }
    }
    let 右子树累计值 = 0
    if (node.right && (node.right.left || node.right.right)) {
        // 有右孩子 且 不是叶子节点 则继续递归
        右子树累计值 = fn(node.right)
    }
    // 递归出口
    return 左子树累计值 + 右子树累计值
}

// 验证
console.log('递归求和：' + fn(root)) // 1

// 层序遍历
function fn2(root) {
    let result = 0
    let queue = [] // 辅助队列
    queue.push(root)
    while (queue.length) {
        // 注 层序遍历不是非得 let size = queue.length while(size--)
        // 当需要按层划分运算时 为了区分每一层 才这样做
        // 只为了遍历的话 一边遍历一边往队列末尾添加元素就行
        let node = queue.shift()
        if (node.left) {
            // 有左孩子
            if (node.left.left == null && node.left.right == null) {
                // 左孩子是叶子节点 统计值 并且不对其遍历
                result += node.left.value
            } else {
                // 不是叶子节点 装入队列进行遍历
                queue.push(node.left)
            }
        }
        // 右孩子存在 装入队列遍历
        node.right && queue.push(node.right)
    }
    return result
}

// 验证
console.log('层序遍历求和：' + fn2(root)) // 1