SOURCE

// 思路
// 递归实现
// 单层递归逻辑 分三种情况
// 一方有而另一方没有 则取有值的一方 并不再往下递归
// 双方都有值 则合并值 并继续同步往下递归
// 双方都没有值 则返回null
// 迭代(层序)实现
// 同步遍历 即两个二叉树每次循环各取一个节点 判断两个树当前节点 左右子节点情况
// 两个树当前节点的孩子节点都 遵循两种情况
// 孩子节点 都不为空 则合并值 装入队列 继续同步遍历
// 孩子节点 有一个为空 则跳过遍历 将有值一方的子树作为结果

let root1 = {
    value: 1,
    left: {
        value: 3,
        left: {
            value: 5
        }
    },
    right: {
        value: 2
    }
}
let root2 = {
    value: 2,
    left: {
        value: 1,
        right: {
            value: 4
        }
    },
    right: {
        value: 3,
        right: {
            value: 7
        }
    }
}

// 递归实现
function fn1(node1, node2) {
    // 递归出口
    if (node1 == null) {
        // node1为空 则取node2为结果(node2为空则返回null)
        return node2
    } else if (node2 == null) {
        // node1不为空 且 node2为空 则取node1为结果
        return node1
    }
    // node1 和 node2 都不为空 则合并值 并向下递归
    // 以构造新二叉树为例
    let result = {
        value: node1.value + node2.value
    }
    result.left = fn1(node1.left, node2.left) || null
    result.right = fn1(node1.right, node2.right) || null
    return result
}

// 验证
console.log('递归实现', fn1(root1, root2))

// 层序遍历
function fn2(root1, root2) {
    // 辅助队列
    let queue = []
    // 初始值
    queue.push(root1)
    queue.push(root2)
    while (queue.length) {
        // 一次弹出两个节点
        let node1 = queue.shift()
        let node2 = queue.shift()
        // 对应位置节点 值进行合并
        // 以在原有二叉树基础上修改为例
        node1.value += node2.value
        // 以当前节点 判断子节点是否为空 并进行比较
        if (node1.left && node2.left) {
            // 孩子节点都不为空 则将对应位置节点装入队列
            queue.push(node1.left)
            queue.push(node2.left)
        } else if (node1.left == null) {
            // 有一方孩子节点为空 或 两者孩子节点都为空
            // node1孩子节点不为空 则不操作 取node1为结果
            // node1孩子节点为空 node2孩子节点无论是否为空 取node2为结果
            node1.left = node2.left || null
            // 因为node1复制node2子树 因此该子树与node2子树完全相同
            // 没必要装入队列 进行比较
        }
        // 右子节点同左子节点
        if (node1.right && node2.right) {
            queue.push(node1.right, node2.right)
        } else if (node1.right == null) {
            node1.right = node2.right || null
        }
    }
    return root1
}

// 验证
let root3 = JSON.parse(JSON.stringify(root1))
console.log('层序遍历', fn2(root3, root2))