前端就该用 JS 刷算法22

每日一题 -- 树

1530. 好叶子节点对的数量

1530. 好叶子节点对的数量

分析

1. 看到根据距离判断的时候，首先看是是用 bfs 在一层中进行比较，还是走 dfs，要从一个树节点途径某个枢纽节点，再到另一棵树的节点，这道题属于后者
2. 既然是需要枢纽节点，且比较的是叶子节点，也就是需要用到前序遍历，自底向上获取到枢纽节点到叶子结点距离的所有值；
3. 由于是从一个叶子节点到另外一个叶子节点，所以枢纽节点也必须分左右两子树的距离数组，分别进行匹配

// https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs/description/
// 1530. 好叶子节点对的数量
[1530. 好叶子节点对的数量]()

/**
 * @分析
 * 1. 这里求的是好节点对的数量，也就是需要配对的，而不是找出，或者存在
 * 2. 所以要计算数量，得有相应的数据池，然后通过组合的方式进行比较，得出合乎规格的数量
 * 3. 在这里，求的是叶子节点之间路径的匹配，所以数据池就是：当前节点到各个叶子节点的距离
 * 4. 由于求的是最短的距离，所以最好是自低向上来求，所以用前序遍历到叶子节点中去
 * 5. 然后自低向上就可以根据左右子树距离叶子节点的距离，推断出自己到左右两棵子树的叶子节点的距离的数组
 * 6. 由于每一个节点都是连接枢纽，所以通过左右距离数组可以匹配除节点对数量
 */
var countPairs = function (root, distance) {
    let res = 0
    const dfs = root => {
        if (!root) return []
        if (!root.left && !root.right) return [0]
        // 求出到左树叶子节点的距离数组
        const leftArr = dfs(root.left).map(i => i+1)
        // 求出到右树叶子节点的距离数组
        const rightArr = dfs(root.right).map(i => i+1)
        // root 是连接枢纽，所有的匹配都必须走它才能连接。
        for (let l of leftArr) {
            for (let r of rightArr) {
                if(l+r<=distance){
                    res++
                }
            }
        }
        // 最后返回当前节点到所有叶子结点距离的数组
        return [...leftArr,...rightArr]
    }
    dfs(root)
    return res
};