SOURCE

// 思路
// 递归实现
// 本题是要找一条符合要求的 路径 因此递归出口就是叶子节点
// 在到达叶子节点的过程中 进行累加或累减
// 等到叶子节点后 判断累加/累减值是否符合 从而返回结果
// 需要注意的是 因为不需要遍历整棵树 找到符合的路径就结束
// 因此需要 处理返回值 为不影响右子树遍历 要选择性返回
// 迭代实现
// 本质还是要找一条符合的路径 因此必须有 回溯
// 但是迭代要实现回溯 就必须记录每一个节点继承自父节点的数据
// 因此需要用一个数组来 一一对应 每层节点

let root = {
    value: 5,
    left: {
        value: 4,
        left: {
            value: 11,
            left: {
                value: 7
            },
            right: {
                value: 2
            }
        }
    },
    right: {
        value: 8,
        left: {
            value: 13
        },
        right: {
            value: 4,
            left: {
                value: 5
            },
            right: {
                value: 1
            }
        }
    }
}

// 递归实现
function fn(node, 累计值, 目标值 = 22) {
    // 递归出口 遍历到叶子节点
    if (node.left == null && node.right == null) {
        return 累计值 == 目标值
    }
    // 还没到叶子节点
    if (node.left) {
        // 一旦找到符合的路径 就结束整个递归 因此要处理返回值
        // 不能写成 node.left && 这种简写形式
        // 如果当前递归返回结果为true 那么不再继续往下执行
        if (fn(node.left, 累计值 + node.left.value, 目标值)) return true
    }
    // 左子树递归遍历没找到符合的路径 则继续右子树遍历
    if (node.right) {
        if (fn(node.right, 累计值 + node.right.value, 目标值)) return true
    }
    // 当前节点 的左右子树递归完还没找到符合的路径 说明包含当前节点的 子树整体结果为false
    return false
}

// 验证
console.log('递归实现：' + fn(root, root.value)) // true

// 层序遍历
function fn2(root, 目标值 = 22) {
    let queue = [] // 辅助队列
    queue.push(root)
    // 关键点 创建一个数组 对应 每层节点
    let 累计值数组 = [0] // 第一层是根节点 因此只有一个元素
    while (queue.length) {
        // 累计值数组 其实对应的是 每个节点
        // 因此不需要 再内嵌一个循环 分层进行处理
        // 只要每出队列一个元素 装入累计值数组的元素能对应上其子节点就行
        let node = queue.shift()
        // 关键点 当前节点出队列 则 对应 累计值数组中的元素就要出队列
        let 当前值 = 累计值数组.shift()
        // 与当前节点值 进行累计
        当前值 += node.value
        // 先判断是否到达了叶子节点 且 是否符合
        if (node.left == null && node.right == null && 当前值 == 目标值) {
            return true
        }
        // 当前节点不是叶子节点 或 路径不符合 则继续向下执行
        if (node.left) {
            queue.push(node.left)
            // 关键点 存在子节点 则将当前节点的数据 继承给 对应 子节点
            累计值数组.push(当前值)
        }
        if (node.right) {
            queue.push(node.right)
            累计值数组.push(当前值)
        }
    }
    return false
}

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