513. 找树左下角的值

[zpc7]

513. 找树左下角的值

var findBottomLeftValue = function (root) {
    let curVal //将要返回的值
    let curHeight = 0; // 当前遍历在树结构的第几层

    const dfs = (root, height) => {
        // 空节点,返回
        if (!root) {
            return;
        }
        height++;
        // 先左后右
        dfs(root.left, height);
        dfs(root.right, height);
        // 上面是先左后右, 在执行左边的时候, 下面会 先 更改curHeight, 所以右边的时候不会进入条件
        if (height > curHeight) {
            curHeight = height;
            curVal = root.val;
        }
    }

    dfs(root, 0);
    return curVal;

};

// 示例代码
const data = {
    val: 2,
    left: {
        val: 1
    },
    right: {
        val: 3
    }
}

// dfs 执行顺序:
// 1. 执行dfs(left)之前 height = 1, root = data 
// 2. 执行dfs(left), 遇到新的dfs(left) 之前 root = {val:1} height = 2
// 3. 执行新的dfs(left), 此时root 是undefined 返回
// 4. 执行第2中的 dfs(right), 此时root 是undefined 返回
// 5. 回到第2, 去执行dfs(right)后面的代码, 更新curHeight = 2, curVal = 1
// 6. 回到第1, 去执行dfs(right), 此时root = data, height = 1
// 7. 执行dfs(left)前, height = 2, root = (val:3)
// 8. 同样的undefined的判断...省略
// 9.  回到第1, 执行dfs(right)后面的代码, 此时不满足height > curHeight, 不会进条件

findBottomLeftValue(data)