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(root) {
    let result = 0
    let queue = [] // 辅助队列
    // 将根节点填入
    queue.push(root)
    while (queue.length) {
        let size = queue.length
        for (let i = 0; i < size; i++) {
            let node = queue.shift()
            // 只记录每层第一个值
            if (i == 0) {
                result = node.value
            }
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return result
}

// 验证
console.log('层序遍历结果：' + fn(root)) // 1

// 递归实现
function fn2(root) {
    let result = 0
    let 最大深度 = 0 // 用于判断是否更新记录值的标识
    function 递归(node, 当前深度) {
        // 递归出口 叶子节点
        if (node.left == null && node.right == null) {
            if (当前深度 > 最大深度) {
                // 第一次进入更深的节点 更新标识 记录当前节点值
                最大深度 = 当前深度
                result = node.value
            }
            // 叶子节点没有下一层 返回上一层递归
            return
        }
        // 必须先递归进入左节点
        // 注意 这里其实用了隐性 回溯
        // 因为递归进入子节点时 深度会+1 但是递归出栈返回当前节点时深度要回溯到之前值
        // 因此在递归传递值时+1 不影响当前节点记录的深度 从而达到隐性回溯
        node.left && 递归(node.left, 当前深度 + 1)
        node.right && 递归(node.right, 当前深度 + 1)
    }
    递归(root, 1)
    return result
}

// 验证
console.log('递归实现结果：' + fn2(root)) // 1