前端就该用 JS 刷算法19

每日一题 -- 树

783. 二叉搜索树节点最小距离

783. 二叉搜索树节点最小距离

二叉树的特性求解

• 二叉搜索树一出，就应该考虑中序遍历，然后题目求的是最小距离，那必然是两个单增数列中响铃的两个节点之差
• 由于求差，所以不需要维护数组，只要变量即可

// https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
// 783. 二叉搜索树节点最小距离

/**
 * @分析
 * 1. 看到二叉搜索树就想到中序遍历是一个有序递增数组，最小的肯定是在相邻的节点之间
 */
var minDiffInBST = function (root) {
    if (!root) return 0
    let min = Infinity
    let temp = null
    const dfs = root => {
        if (!root) return
        dfs(root.left)
        if (temp) {
            min = Math.min(min, root.val - temp)
        }
        temp = root.val
        dfs(root.right)
    }
    dfs(root)
    return min
};

参数扩展大发法

• 我们求整棵树的极值的时候，可以想到求两科子树符合条件的值，然后最后比较返回最终值即可
• 这里用到的是自顶向下的思考方式，然后要求的是最小值，所以在遍历过程中，携带最大和最小两个扩展参数，即可求得相应的值
• 对于根节点而言，直接正反无穷就是最大最小值
• 对于子树节点而言，向下递归过程需要考虑缩小最大或者最小值，以求得真实的解
• 在这里由于是二叉搜索树，所以在左树递归的时候，根节点的值肯定大于左树的所有值，所以 upper 是 root.val
• 同理，右子树中，根节点的值肯定是最小值
• 这种方式可以处理非二叉搜索树的其他办法

/**
 * 扩展参数法
 * @分析
 * 1. 自顶向下求子树中最小的距离
 */
var minDiffInBST = function (root) {

    const dfs = (root, lower, upper) => {
        if (!root) return upper - lower
        const left = dfs(root.left, lower, root.val)
        const right = dfs(root.right, root.val, upper)
        return Math.min(left, right)
    }
    return dfs(root, -Infinity, Infinity)
}

91算法 -- 搜索

113. 路径总和 II

113. 路径总和 II

// https://leetcode-cn.com/problems/path-sum-ii/
// 113. 路径总和 II

/**
 * 
 * @分析
 * 1. 必须是根节点到叶子节点的路径，所以截止条件就是叶子条件
 * 2. 找和，那就需要自顶向下计算值，所以扩展参数记录总和值
 * 3. 最后返回的是路径数组，所以还得给一个扩展参数为数组
 */
var pathSum = function(root, sum) {
    if(!root) return []
    const res = []
    const dfs = (root,num,arr) => {
        const temp = num+root.val
        if(!root.left && !root.right){
            if(temp === sum){
                res.push([...arr,root.val])
            }
            return
        }
        if(root.left){
            dfs(root.left,temp,[...arr,root.val])
        }
        if(root.right){
            dfs(root.right,temp,[...arr,root.val])
        }
    }
    dfs(root,0,[])
    return res
};